fork(1) download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. /* нахождение пути*/
  6. void find_path(int n, int row, int col, char** lab, int** visited, int** path, queue<int>& plan){
  7. 	if(!visited[row][col]){
  8. 		/* проверяем не вышли ли мы за границы лабиринта, есть ли клетка 
  9. 		в массиве посещенных и можно ли через нее пройти*/
  10. 		if ((row+1) < n && (row+1) >= 0 && !visited[row+1][col] &&
  11. 			(lab[row+1][col] == '.' || lab[row+1][col] == 'X')) {
  12. 				path[row+1][col] = path[row][col] + 1;
  13. 				plan.push(row+1);
  14. 				plan.push(col);
  15. 		}
  16. 		if((row-1) < n && (row-1) >= 0 && !visited[row-1][col] && 
  17. 			(lab[row-1][col] == '.' || lab[row-1][col] == 'X')) {
  18. 				path[row-1][col] = path[row][col] + 1;
  19. 				plan.push(row-1);
  20. 				plan.push(col);
  21. 		}
  22. 		if((col + 1) < n && (col + 1) >= 0 && !visited[row][col+1] && 
  23. 			(lab[row][col+1] == '.' || lab[row][col+1] == 'X')) {
  24. 				path[row][col+1] = path[row][col] + 1;
  25. 				plan.push(row);
  26. 				plan.push(col+1);
  27. 		}
  28. 		if((col - 1) < n && (col - 1) >= 0 && !visited[row][col-1] && 
  29. 			(lab[row][col-1] == '.' || lab[row][col-1] == 'X')) {
  30. 				path[row][col-1] = path[row][col] + 1;
  31. 				plan.push(row);
  32. 				plan.push(col-1);
  33. 		}
  34. 		visited[row][col] = 1; /* отмечаем клетку в которой побывали */
  35. 	}
  36. }
  37.  
  38. int main() {
  39. 	int n, x_start, y_start, x_end, y_end, x, y;
  40. 	queue <int> plan; 
  41. 	cin >> n;
  42. 	char** lab = new char* [n];
  43. 	int** visited = new int * [n];
  44. 	int** path = new int * [n];
  45. 	for(int i=0; i<n; i++){
  46. 		lab[i] = new char [n];   /* массив для хранения лабиринта */
  47. 		visited[i] = new int [n]; /* массив для хранения информации о посещении клеток*/
  48. 		path[i] = new int [n];  /* массив для хранения найденных путей */
  49. 		for(int j=0; j<n; j++){
  50. 			visited[i][j] = 0;  
  51. 			path[i][j] = -1;   
  52. 			cin >> lab[i][j]; 
  53. 			if (lab[i][j] == '@') { /* находим начало пути*/
  54. 				x_start = i;
  55. 				y_start = j;
  56. 				plan.push(i);  /* заносим начальную клетку */
  57. 				plan.push(j);  /* в план посещения */
  58. 				path[i][j] = 1;
  59. 			}
  60. 			else if (lab[i][j] == 'X') { /* находим конечную точку */
  61. 				x_end = i;
  62. 				y_end = j;
  63. 			}
  64. 		}
  65. 	}
  66. 	while(!plan.empty()){ /* пока очередь посещения клеток непустая*/
  67. 		x=plan.front();
  68. 		plan.pop();
  69. 		y=plan.front();
  70. 		plan.pop();
  71. 		find_path(n, x, y, lab, visited, path, plan); /* продолжаем поиск пути*/
  72. 	}
  73. 	if(!visited[x_end][y_end]){
  74. 		cout << "N" << endl;
  75. 	}
  76. 	else {
  77. 		cout << "Y" << endl;
  78. 			x = x_end;
  79. 			y = y_end;
  80. 			lab[x][y] = '+';
  81. 			while (path[x][y] != 2) { /* восстановление пути*/
  82. 				if ((x-1) >= 0 && (x-1) < n && (path[x-1][y] == path[x][y] - 1)) {
  83. 					x = x-1;
  84. 					lab[x][y] = '+';
  85. 				}
  86. 				else if ((x+1) >= 0 && (x+1) < n && (path[x+1][y] == path[x][y] - 1)) {
  87. 					x = x+1;
  88. 					lab[x][y] = '+';
  89. 				}
  90. 				else if ((y-1) >= 0 && (y-1) < n && (path[x][y-1] == path[x][y] - 1)) {
  91. 					y = y-1;
  92. 					lab[x][y] = '+';
  93. 				}
  94. 				else if ((y+1) >= 0 && (y+1) < n && (path[x][y+1] == path[x][y] - 1)) {
  95. 					y = y+1;
  96. 					lab[x][y] = '+';
  97. 				}
  98. 			}
  99. 			for (int i = 0; i < n; i++) {
  100. 				for (int j = 0; j < n; j++) {
  101. 					cout << lab[i][j];
  102. 				}
  103. 				cout << endl;
  104. 			}
  105. 		}
  106. 	return 0;
  107. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
5
...X.
.....
O.OOO
.....
....@
stdout
copy 
Y
...+.
.+++.
O+OOO
.+...
.+++@
https://ideone.com/DoxJel
1060
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

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!