Advertisement
Guest User

Untitled

a guest
Mar 31st, 2020
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. const int inf = 1e9;
  8.  
  9. vector < pair < int, int > > shift = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
  10.  
  11. int main() {
  12.     int n;
  13.     cin >> n;
  14.  
  15.     vector < vector < char > > a(n, vector < char >(n));
  16.    
  17.     pair < int, int > start, finish;
  18.  
  19.     for (int i = 0; i < n; i++) {
  20.         for (int j = 0; j < n; j++) {
  21.             cin >> a[i][j];
  22.             if (a[i][j] == '@') {
  23.                 start = { i, j };
  24.             }
  25.             if (a[i][j] == 'X') {
  26.                 finish = { i, j };
  27.             }
  28.         }
  29.     }
  30.  
  31.     vector < vector < bool > > used(n, vector < bool >(n, false));
  32.     vector < vector < int > > dist(n, vector < int >(n, inf));
  33.     vector < vector < pair < int, int > > > par(n, vector < pair < int, int > >(n, {-1, -1}));
  34.    
  35.     queue < pair < int, int > > Q;
  36.     Q.push(start);
  37.     used[start.first][start.second] = true;
  38.     dist[start.first][start.second] = 0;
  39.  
  40.     while (Q.size() != 0) {
  41.         pair < int, int > v = Q.front();
  42.         Q.pop();
  43.        
  44.         int x = v.first;
  45.         int y = v.second;
  46.  
  47.         for (int i = 0; i < shift.size(); i++) {
  48.             int nx = v.first + shift[i].first;
  49.             int ny = v.second + shift[i].second;
  50.  
  51.             if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
  52.                 if (used[nx][ny] == false && a[nx][ny] != 'O') {
  53.                     dist[nx][ny] = dist[x][y] + 1;
  54.                     used[nx][ny] = true;
  55.                     par[nx][ny] = { x, y };
  56.                     Q.push({ nx, ny });
  57.                 }
  58.             }
  59.         }
  60.     }
  61.  
  62.     if (dist[finish.first][finish.second] == inf) {
  63.         cout << "N";
  64.         system("pause");
  65.         return 0;
  66.     }
  67.  
  68.     int tx = finish.first, ty = finish.second;
  69.  
  70.     while (par[tx][ty] != make_pair(-1, -1)) {
  71.         a[tx][ty] = '+';
  72.         int qx = par[tx][ty].first;
  73.         int qy = par[tx][ty].second;
  74.         tx = qx;
  75.         ty = qy;
  76.     }
  77.  
  78.     cout << "Y\n";
  79.  
  80.     for (int i = 0; i < n; i++) {
  81.         for (int j = 0; j < n; j++) {
  82.             cout << a[i][j];
  83.         }
  84.         cout << "\n";
  85.     }
  86.  
  87.     system("pause");
  88.     return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement