ccbeginner

TOJ 449

Feb 17th, 2020
254
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //TOJ
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int toNum(char c){
  6.     if(c == '.' || c == '*')return 0;
  7.     if(c == '#')return 1;
  8.     if(c == 'R')return 2;
  9.     if(c == 'G')return 3;
  10.     if(c == 'B')return 4;
  11.     if(c == 'Y')return 5;
  12.     if(c == 'X')return -1;
  13.     return -toNum(c-32);
  14. }
  15.  
  16. int maze[100][100];
  17. bool vis[100][100][1<<6];
  18.  
  19. struct stat{
  20.     int x, y;
  21.     int key = 0;
  22.     int step = 0;
  23. };
  24.  
  25. int dx[] = {0,1,0,-1};
  26. int dy[] = {1,0,-1,0};
  27.  
  28. int32_t main(){
  29.     int n,m;
  30.     char c;
  31.     stat one;
  32.     cin >> n >> m;
  33.     for(int i = 0; i < n; ++i){
  34.         for(int j = 0; j < m; ++j){
  35.             cin >> c;
  36.             if(c == '*'){
  37.                 one.x = i;
  38.                 one.y = j;
  39.             }
  40.             maze[i][j]= toNum(c);
  41.         }
  42.     }
  43.     deque<stat> dq;
  44.     dq.emplace_back(one);
  45.     int ans = -1;
  46.     while(!dq.empty() && ans == -1){
  47.         stat tmd = dq.front();
  48.         dq.pop_front();
  49.         //cout << tmd.x << ' ' << tmd.y << ' ' << tmd.key << ' ' <<  tmd.step << '\n';
  50.         for(int i = 0; i < 4; ++i){
  51.             int nx = tmd.x + dx[i];
  52.             int ny = tmd.y + dy[i];
  53.             if(!(0 <= nx && nx < n && 0 <= ny && ny < m))continue;
  54.             if(maze[nx][ny] >= 1 && !(tmd.key & (1<<maze[nx][ny])))continue;
  55.             //cout << ' ' << nx << ' ' << ny << '\n';
  56.             if(maze[nx][ny] == -1){
  57.                 ans = tmd.step+1;
  58.                 break;
  59.             }
  60.             stat nxt = {.x = nx, .y = ny, .key = tmd.key, .step = tmd.step+1};
  61.             if(maze[nx][ny] <= -2)nxt.key |= (1<<-maze[nx][ny]);
  62.             //cout << ' ' << nxt.x << ' ' << nxt.y << ' ' << nxt.key << '\n';
  63.             if(vis[nxt.x][nxt.y][nxt.key])continue;
  64.             vis[nxt.x][nxt.y][nxt.key] = 1;
  65.             dq.emplace_back(nxt);
  66.         }
  67.     }
  68.     if(ans != -1)cout << "Escape possible in " << ans << " steps.\n";
  69.     else cout << "The poor student is trapped!\n";
  70.     return 0;
  71. }
RAW Paste Data