ccbeginner

E-Olymp 1060

Oct 1st, 2020
1,167
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define SZ(X) ((int)(X).size())
  5.  
  6. pair<int,int> que[10000];
  7. int head=0, tail=0;
  8.  
  9. bool grid[40][40];
  10. char out[40][40];
  11. pair<int,int> back[40][40];
  12. int dx[] = {0,1,0,-1};
  13. int dy[] = {1,0,-1,0};
  14.  
  15. int32_t main(){
  16.     int n;
  17.     cin >> n;
  18.     pair<int,int> s,e;
  19.     for(int i = 0; i < n; ++i){
  20.         for(int j = 0; j < n; ++j){
  21.             char c;
  22.             cin >> c;
  23.             if(c == 'X')s = make_pair(i,j);
  24.             else if(c == '@')e = make_pair(i,j);
  25.             if(c == 'O')grid[i][j] = 1;
  26.             else grid[i][j] = 0;
  27.             out[i][j] = c;
  28.         }
  29.     }
  30.     back[s.first][s.second] = make_pair(-1,-1);
  31.     grid[s.first][s.second] = 1;
  32.     que[tail++] = s;
  33.     bool yes = 0;
  34.     while(tail - head > 0 && !yes){
  35.         pair<int,int> tmd = que[head++];
  36.         if(tmd == e)break;
  37.         for(int i = 0; i < 4 && !yes; ++i){
  38.             int nx = tmd.first+dx[i];
  39.             int ny = tmd.second+dy[i];
  40.             if(0 <= nx && nx < n && 0 <= ny && ny < n && !grid[nx][ny]){
  41.                 back[nx][ny] = tmd;
  42.                 que[tail++] = make_pair(nx,ny);
  43.                 grid[nx][ny] = 1;
  44.                 if(make_pair(nx, ny) == e)yes = 1;
  45.             }
  46.         }
  47.     }
  48.     if(yes){
  49.         cout << 'Y' << '\n';
  50.         while(e != s){
  51.             e = back[e.first][e.second];
  52.             out[e.first][e.second] = '+';
  53.         }
  54.         for(int i = 0; i < n; ++i){
  55.             for(int j = 0; j < n; ++j)cout << out[i][j];
  56.             cout << '\n';
  57.         }
  58.     }else cout << 'N' << '\n';
  59.     return 0;
  60. }
RAW Paste Data