kananasgarli90

Labyrinth

Oct 26th, 2020
799
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. char adj[1001][1001];
  4. int color[1001][1001], dis[1001][1001], p[1001][1001], id[1001][1001], k;
  5. int n, m, a1, a2, b1, b2;
  6. int parent(int x, int y){
  7.     return id[x][y];
  8. }
  9.  
  10.  
  11. void bfs(){
  12.     queue<pair<int, int> > q;
  13.     color[a1][a2] = 1;
  14.     q.push(make_pair(a1, a2));
  15.     while(q.size() != 0){
  16.         int x = q.front().first;
  17.         int y = q.front().second;
  18.         if(x + 1 <= n && color[x+1][y] == 0 && adj[x+1][y] == '.'){
  19.             q.push(make_pair(x+1, y));
  20.             dis[x+1][y] = dis[x][y] + 1;
  21.             color[x+1][y] = 1;
  22.             p[x+1][y] = parent(x, y);
  23.         }
  24.         if(x - 1 >= 1 && color[x-1][y] == 0 && adj[x-1][y] == '.'){
  25.             q.push(make_pair(x-1, y));
  26.             dis[x-1][y] = dis[x][y] + 1;
  27.             color[x-1][y] = 1;
  28.             p[x-1][y] = parent(x, y);
  29.         }
  30.         if(y + 1 <= m && color[x][y+1] == 0 && adj[x][y+1] == '.'){
  31.             q.push(make_pair(x, y+1));
  32.             dis[x][y+1] = dis[x][y] + 1;
  33.             color[x][y+1] = 1;
  34.             p[x][y+1] = parent(x, y);
  35.         }
  36.         if(y - 1 >= 1 && color[x][y-1] == 0 && adj[x][y-1] == '.'){
  37.             q.push(make_pair(x, y-1));
  38.             dis[x][y-1] = dis[x][y] + 1;
  39.             color[x][y-1] = 1;
  40.             p[x][y-1] = parent(x, y);
  41.         }
  42.         q.pop();
  43.         color[x][y] = 1;
  44.     }
  45. }
  46.  
  47. void printPath(int x, int y){
  48.     int parent_id = p[x][y];
  49.     if(parent_id == 0){
  50.         return;
  51.     }
  52.     if(x-1 >= 1 && id[x-1][y] == parent_id){
  53.         printPath(x-1, y);
  54.         cout<<"D";
  55.     }
  56.     if(x+1 <= n && id[x+1][y] == parent_id){
  57.         printPath(x+1, y);
  58.         cout<<"U";
  59.     }
  60.     if(y-1 >= 1 && id[x][y-1] == parent_id){
  61.         printPath(x, y-1);
  62.         cout<<"R";
  63.     }
  64.     if(y+1 <= m && id[x][y+1] == parent_id){
  65.         printPath(x, y+1);
  66.         cout<<"L";
  67.     }
  68.  
  69. }
  70. int main()
  71. {
  72.     cin>>n>>m;
  73.     for(int i = 1; i <= n; i++){
  74.         for(int j = 1; j <= m; j++){
  75.             cin>>adj[i][j];
  76.             id[i][j] = ++k;
  77.             if(adj[i][j] == 'A'){
  78.                 a1 = i;
  79.                 a2 = j;
  80.             }
  81.             if(adj[i][j] == 'B'){
  82.                 b1 = i;
  83.                 b2 = j;
  84.                 adj[i][j] = '.';
  85.             }
  86.         }
  87.     }
  88.     bfs();
  89.     if(color[b1][b2] == 1){
  90.         cout<<"YES"<<endl;
  91.         cout<<dis[b1][b2]<<endl;
  92.         printPath(b1, b2);
  93.     }
  94.     else{
  95.         cout<<"NO"<<endl;
  96.     }
  97. }
  98.  
RAW Paste Data