ccbeginner

UVa Q589

Jan 23rd, 2020
109
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q589
  2. #include <bits/stdc++.h>
  3. using namespace std ;
  4.  
  5. struct stat {
  6.     int Bx, By, Sx, Sy;
  7.     bool operator!=(const stat &x){return Bx != x.Bx || By != x.By || Sx != x.Sx || Sy != x.Sy;}
  8. }pre[20][20][20][20];
  9. bool maze[20][20];
  10. bool vis[20][20][20][20];//Bx, By, Sx, Sy
  11.  
  12. int dx[] = {0,1,0,-1};
  13. int dy[] = {1,0,-1,0};
  14. char out[] = {'e', 's', 'w', 'n'};
  15.  
  16. int32_t main(){
  17.     int n,m,cnt = 0;
  18.     stat one;
  19.     char c;
  20.     while(cin >> n >> m){
  21.         if(n == 0 && m == 0)break;
  22.         memset(vis, 0, sizeof(vis));
  23.         memset(maze, 0, sizeof(maze));
  24.         int Tx, Ty;
  25.         for(int i = 0; i < n; ++i){
  26.             for(int j = 0; j < m; ++j){
  27.                 cin >> c;
  28.                 if(c == 'S'){
  29.                     one.Sx = i;
  30.                     one.Sy = j;
  31.                 }else if(c == 'B'){
  32.                     one.Bx = i;
  33.                     one.By = j;
  34.                 }else if(c == 'T'){
  35.                     Tx = i;
  36.                     Ty = j;
  37.                 }
  38.                 maze[i][j] = (c == '#')? 1 : 0;
  39.             }
  40.         }
  41.         //BFS
  42.         deque<stat> dq, brt;
  43.         vis[one.Bx][one.By][one.Sx][one.Sy] = 1;
  44.         dq.emplace_back(one);
  45.         stat tail;
  46.         bool fnd = 0;
  47.         while(!dq.empty() && !fnd){
  48.             stat tmd = dq.front();
  49.             dq.pop_front();
  50.             if(tmd.Bx == Tx && tmd.By == Ty){
  51.                 tail = tmd;
  52.                 fnd = 1;
  53.                 break;
  54.             }
  55.             do{
  56.                 //cout << tmd.Bx << ' ' << tmd.By << ' ' << tmd.Sx << ' ' << tmd.Sy << endl;
  57.                 for(int i = 0; i < 4; ++i){
  58.                     int nx = tmd.Sx+dx[i], ny = tmd.Sy+dy[i];
  59.                     if(0 <= nx && nx < n && 0 <= ny && ny < m && !maze[nx][ny]){
  60.                         if(nx == tmd.Bx && ny == tmd.By){
  61.                             if(0 <= tmd.Bx+dx[i] && tmd.Bx+dx[i] < n && 0 <= tmd.By+dy[i] && tmd.By+dy[i] < m){
  62.                                 stat nxt = {.Bx = tmd.Bx+dx[i], .By = tmd.By+dy[i], .Sx = nx, .Sy = ny};
  63.                                 if(vis[nxt.Bx][nxt.By][nxt.Sx][nxt.Sy])continue;
  64.                                 vis[nxt.Bx][nxt.By][nxt.Sx][nxt.Sy] = 1;
  65.                                 pre[nxt.Bx][nxt.By][nxt.Sx][nxt.Sy] = tmd;
  66.                                 dq.emplace_back(nxt);
  67.                                 if(nxt.Bx == Tx && nxt.By == Ty){
  68.                                     tail = nxt;
  69.                                     fnd = 1;
  70.                                     break;
  71.                                 }
  72.                             }
  73.                         }else{
  74.                             stat nxt = {.Bx = tmd.Bx, .By = tmd.By, .Sx = nx, .Sy = ny};
  75.                             if(vis[nxt.Bx][nxt.By][nxt.Sx][nxt.Sy])continue;
  76.                             vis[nxt.Bx][nxt.By][nxt.Sx][nxt.Sy] = 1;
  77.                             pre[nxt.Bx][nxt.By][nxt.Sx][nxt.Sy] = tmd;
  78.                             brt.emplace_back(nxt);
  79.                         }
  80.                     }
  81.                 }
  82.                 if(!brt.empty()){
  83.                     tmd = brt.front();
  84.                     brt.pop_front();
  85.                 }else break;
  86.             }while(1);
  87.         }
  88.         cout << "Maze #" << ++cnt << "\n";
  89.         if(fnd){
  90.             vector<stat> v;
  91.             while(tail != one){
  92.                 v.emplace_back(tail);
  93.                 //cout << tail.Bx << ' ' << tail.By << ' ' << tail.Sx << ' ' << tail.Sy << endl;
  94.                 tail = pre[tail.Bx][tail.By][tail.Sx][tail.Sy];
  95.             }
  96.             //cout << tail.Bx << ' ' << tail.By << ' ' << tail.Sx << ' ' << tail.Sy << endl;
  97.             while(!v.empty()){
  98.                 for(int i = 0; i < 4; ++i){
  99.                     if(tail.Sx+dx[i] == v.back().Sx && tail.Sy+dy[i] == v.back().Sy){
  100.                         c = out[i];
  101.                         if(tail.Bx != v.back().Bx || tail.By != v.back().By)c -= 32;
  102.                         cout << c;
  103.                         break;
  104.                     }
  105.                 }
  106.                 tail = v.back();
  107.                 v.pop_back();
  108.             }
  109.             cout << '\n';
  110.         }else{
  111.             cout << "Impossible.\n";
  112.         }
  113.         cout << '\n';
  114.     }
  115.     return 0 ;
  116. }
RAW Paste Data