fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const long long OO = 1e7;
  6. const long long mod = 1e9 + 7;
  7. const long double EPS = (1e-18);
  8. int dcmp(long double x, long double y) { return fabs(x - y) <= EPS ? 0 : x < y ? -1 : 1; }
  9.  
  10. int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
  11. int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
  12.  
  13.  
  14. void fast(){
  15. #ifndef ONLINE_JUDGE
  16. 	freopen("F:\\solving\\input.txt", "r", stdin);
  17. 	freopen("F:\\solving\\output.txt", "w", stdout);
  18.  
  19. #endif
  20. 	freopen("maze.in", "r", stdin);
  21. 	std::ios_base::sync_with_stdio(0);
  22. 	cin.tie(NULL); cout.tie(NULL);
  23. }
  24. const long long MAX =  100 * 1000 + 1;
  25. int n, m;
  26.  
  27. int X[4], Y[4];
  28. int level[501][501][(1<<4)];
  29. char g[501][501];
  30. string s = "abc";
  31. string w = "ABC";
  32. map <  pair< int, int> , int > mp;
  33.  
  34. bool isv(int i, int j , int mask){
  35. 	if (i >= 0 && i < n&&j >= 0 && j < m){
  36. 		if (g[i][j] == 'A' && (mask & 1) == 0)
  37. 			return 0; 
  38. 		if (g[i][j] == 'B' && (mask & 1 << 1) == 0)
  39. 			return 0;
  40. 		if (g[i][j] == 'C' && (mask & 1 << 2) == 0)
  41. 			return 0;
  42. 		return 1;
  43. 	}
  44. 	return 0;
  45. }
  46. int bfs(int i, int j ){
  47. 	memset(level, -1, sizeof level);
  48.  
  49. 	queue<pair< int, pair< int, int> > >q;
  50. 	q.push({ 0 ,{ i, j } });
  51. 	level[i][j][0] = 0;
  52. 	while (q.size() > 0){
  53. 		auto cur = q.front();
  54. 		q.pop();
  55.  
  56. 		if (g[cur.second.first][cur.second.second] == 'E')
  57. 			return level[cur.second.first][cur.second.second][cur.first];
  58. 		for (int d = 0; d < 4; d++){
  59. 			int ii = dx[d] + cur.second.first, jj = dy[d] + cur.second.second;
  60.  
  61.  
  62. 			if (isv(ii, jj , cur.first) && level[ii][jj][cur.first] == -1){
  63. 				int tmp = cur.first;
  64. 				if (g[ii][jj] == 'a'){
  65. 					tmp |= (1 << 0);
  66. 				}
  67. 				else if (g[ii][jj] == 'b'){
  68. 					tmp |= (1 << 1);
  69. 				}
  70. 				else if (g[ii][jj] == 'c'){
  71. 					tmp |= (1 << 2);
  72. 				}
  73. 				q.push({ tmp, { ii, jj } });
  74. 				level[ii][jj][tmp] = level[cur.second.first][cur.second.second][cur.first] + 1;
  75. 			}
  76. 		}
  77. 	}
  78. 	return -1;
  79. }
  80. int main(){
  81. 	fast();
  82. 	int t; cin >> t;
  83. 	while (t--){
  84. 		memset(X, -1, sizeof X);
  85. 		memset(Y, -1, sizeof Y);
  86.  
  87. 		cin >> n >> m;
  88. 		mp.clear();
  89. 		for (int i = 0; i < n; i++){
  90. 			for (int j = 0; j < m; j++){
  91. 				cin >> g[i][j];
  92. 				if (g[i][j] == 'S'){
  93. 					X[0] = i, Y[0] = j;
  94. 				}
  95. 			}
  96. 		}
  97. 		int ret = bfs(X[0], Y[0]);
  98.  
  99. 		cout << ret << endl;
  100. 	}
  101. 	return 0;
  102. }
Runtime error #stdin #stdout #stderr 0s 4356KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/sbb5tz
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!