ccbeginner

UVa Q985

Jan 23rd, 2020
80
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q985
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. bool arr[501][501][4];
  6. bool vis[501][501][4];
  7.  
  8. //{N,E,S,W}
  9. int dx[] = {-1,0,1,0};
  10. int dy[] = {0,1,0,-1};
  11.  
  12. struct stat{
  13.     int step, x, y, t;
  14. };
  15.  
  16. int32_t main(){
  17.     int n,m;
  18.     string s;
  19.     while(cin >> n >> m){
  20.         memset(vis, 0, sizeof(vis));
  21.         memset(arr, 0, sizeof(arr));
  22.         for(int i = 1; i <= n; ++i){
  23.             for(int j = 1; j <= m; ++j){
  24.                 if(i == n && j == m)break;
  25.                 cin >> s;
  26.                 for(int k = 0; k < s.size(); ++k){
  27.                     if(s[k] == 'N')arr[i][j][0] = 1;
  28.                     else if(s[k] == 'E')arr[i][j][1] = 1;
  29.                     else if(s[k] == 'S')arr[i][j][2] = 1;
  30.                     else if(s[k] == 'W')arr[i][j][3] = 1;
  31.                 }
  32.             }
  33.         }
  34.         stat one = {.step = 0, .x = 1, .y = 1, .t = 0};
  35.         deque<stat> dq;
  36.         dq.emplace_back(one);
  37.         int ans = 0;
  38.         while(!dq.empty() && !ans){
  39.             stat tmd = dq.front();
  40.             dq.pop_front();
  41.             //cout << tmd.x << ' ' << tmd.y << ' ' << tmd.t << ' ' << tmd.step << endl;
  42.             for(int i = 0; i < 4; ++i){
  43.                 if(arr[tmd.x][tmd.y][(i-tmd.t+4)%4] == 0)continue;
  44.                 stat nxt = {.step = tmd.step+1, .x = tmd.x+dx[i], .y = tmd.y+dy[i], .t = (tmd.t+1) % 4};
  45.                 //cout << ' ' << nxt.x << ' ' << nxt.y << ' ' << nxt.t << ' ' << nxt.step << endl;
  46.                 if(0 < nxt.x && nxt.x <= n && 0 < nxt.y && nxt.y <= m && !vis[nxt.x][nxt.y][nxt.t]){
  47.                     if(nxt.x == n && nxt.y == m){
  48.                         ans = nxt.step;
  49.                         break;
  50.                     }
  51.                     vis[nxt.x][nxt.y][nxt.t] = 1;
  52.                     dq.emplace_back(nxt);
  53.                 }
  54.             }
  55.         }
  56.         if(ans)cout << ans << '\n';
  57.         else cout << "no path to exit\n";
  58.     }
  59.     return 0 ;
  60. }
RAW Paste Data