Paste Search Dynamic
Recent pastes
trace_back
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 105;
  4.  
  5. int height, width, start_row, start_col;
  6. char grid[N][N];
  7.  
  8. struct point{
  9.     int x, y;
  10. };
  11.  
  12. int dist[N][N];
  13. point pre[N][N];
  14. bool vis[N][N];
  15.  
  16. void trace_back(int x, int y){
  17.     cout << "The distance to reach the end is: " << dist[x][y] << endl;
  18.  
  19.     while(x != start_row || y != start_col){
  20.         if(grid[x][y] == '.')
  21.             grid[x][y] = '+';
  22.  
  23.         point past = pre[x][y];
  24.  
  25.         if(past.x == -1 && past.y == -1)
  26.             break;
  27.  
  28.         x = past.x;
  29.         y = past.y;
  30.  
  31.     }
  32. }
  33.  
  34. bool valid(int x, int y){
  35.     return x >= 1 && x <= height && y >= 1 && y <= width && !vis[x][y] && grid[x][y] != '#';
  36. }
  37.  
  38. void bfs(){
  39.     point q[N * N];
  40.     int elements = 1, cur = 0;
  41.  
  42.     q[0] = {start_row, start_col};
  43.     pre[start_row][start_col] = {-1, -1};
  44.     dist[start_row][start_col] = 0;
  45.  
  46.  
  47.     while(cur < elements){
  48.         point node = q[cur];
  49.         cur++;
  50.  
  51.         if(vis[node.x][node.y])
  52.             continue;
  53.  
  54.         vis[node.x][node.y] = 1;
  55.  
  56.         if(grid[node.x][node.y] == 'e'){
  57.             trace_back(node.x, node.y);
  58.             return;
  59.         }
  60.  
  61.         if(valid(node.x + 1, node.y))
  62.             q[elements] = {node.x + 1, node.y},
  63.             dist[node.x + 1][node.y] = dist[node.x][node.y] + 1,
  64.             pre[node.x + 1][node.y] = node,
  65.             elements++;
  66.  
  67.         if(valid(node.x - 1, node.y))
  68.             q[elements] = {node.x - 1, node.y},
  69.             dist[node.x - 1][node.y] = dist[node.x][node.y] + 1,
  70.             pre[node.x - 1][node.y] = node,
  71.             elements++;
  72.  
  73.         if(valid(node.x, node.y + 1))
  74.             q[elements] = {node.x, node.y + 1},
  75.             dist[node.x][node.y + 1] = dist[node.x][node.y] + 1,
  76.             pre[node.x][node.y + 1] = node,
  77.             elements++;
  78.  
  79.         if(valid(node.x, node.y - 1))
  80.             q[elements] = {node.x, node.y - 1},
  81.             dist[node.x][node.y - 1] = dist[node.x][node.y] + 1,
  82.             pre[node.x][node.y - 1] = node,
  83.             elements++;
  84.     }
  85. }
  86.  
  87. int main(){
  88.     cin >> height >> width;
  89.  
  90.     for(int i = 1; i <= height; i++){
  91.         string line;
  92.         cin >> line;
  93.  
  94.         for(int j = 0; j < line.size(); j++){
  95.             grid[i][j + 1] = line[j];
  96.  
  97.             if(grid[i][j] == 's')
  98.                 start_row = i,
  99.                 start_col = j;
  100.         }
  101.     }
  102.  
  103.     bfs();
  104.  
  105.     for(int i = 1; i <= height; i++){
  106.         for(int j = 1; j <= width; j++)
  107.             cout << grid[i][j];
  108.         cout << endl;
  109.     }
  110. }
Parsed in 0.019 seconds