fork(1) download
  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
stdin
5
...X.
.....
O.OOO
.....
[email protected]
stdout
Y
...+.
.+++.
O+OOO
.+...
[email protected]