fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. class Point {
  6. 	public:
  7. 		char c;
  8. 		bool visited;
  9. 		int i, j, depth;
  10.  
  11. 	Point () {
  12. 		this->visited = false;
  13. 	}
  14. };
  15.  
  16. typedef vector<Point> vP;
  17. typedef vector<vP> vvP;
  18. typedef vector<Point*> queue;
  19.  
  20. int main() {
  21. 	int h, w;
  22. 	cin >> h >> w;
  23.  
  24. 	vvP map(h+2, vP(w+2));
  25. 	queue BFS;
  26.  
  27. 	int i, j;
  28. 	for (i=1; i<=h; i++) {
  29. 		for (j=1; j<=w; j++) {
  30. 			Point& cell = map[i][j];
  31. 			cell.i = i;
  32. 			cell.j = j;
  33.  
  34. 			cin >> cell.c;
  35. 			if (cell.c == 'S') {
  36. 				BFS.emplace_back(&cell);
  37. 				cell.visited = true;
  38. 				cell.depth = 0;
  39. 			}
  40. 		}
  41. 		map[i][0].visited = map[i][j].visited = true;
  42. 	}
  43. 	for (j=1; j<=w; j++)
  44. 		map[0][j].visited = map[i][j].visited = true;
  45.  
  46.  
  47. 	int lifes;
  48. 	cin >> lifes;
  49. 	lifes *= 4;
  50.  
  51.  
  52. 	int depth;
  53. 	int item = 0;
  54. 	do {
  55.  
  56. 		Point*& Position = BFS[item++];
  57.  
  58. 		if (Position->c == 'x')
  59. 			continue;
  60.  
  61. 		if (Position->c == 'T') {
  62. 			cout << "SIM\n";
  63. 			return 0;
  64. 		}
  65.  
  66.  
  67. 		depth = Position->depth + 1;
  68. 		i = Position->i;
  69. 		j = Position->j;
  70.  
  71. 		if (depth <= lifes) {
  72.  
  73. 			Point& North = map[i-1][j];
  74. 			Point& East = map[i][j+1];
  75. 			Point& South = map[i+1][j];
  76. 			Point& West = map[i][j-1];
  77.  
  78. 			if (North.visited == false) {
  79. 				BFS.emplace_back(&North);
  80. 				North.visited = true;
  81. 				North.depth = depth;
  82. 			}
  83. 			if (East.visited == false) {
  84. 				BFS.emplace_back(&East);
  85. 				East.visited = true;
  86. 				East.depth = depth;
  87. 			}
  88. 			if (South.visited == false) {
  89. 				BFS.emplace_back(&South);
  90. 				South.visited = true;
  91. 				South.depth = depth;
  92. 			}
  93. 			if (West.visited == false) {
  94. 				BFS.emplace_back(&West);
  95. 				West.visited = true;
  96. 				West.depth = depth;
  97. 			}
  98.  
  99. 		}
  100.  
  101. 	} while (item < BFS.size());
  102.  
  103. 	cout << "NAO\n";
  104. 	return 0;
  105. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1 6
.S...T
1
stdout
copy 
SIM
https://ideone.com/yHrZIB
language:
C++ (gcc 8.3)
created:
6 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!