mickypinata

CUBE-T153: Seven Gems

Jul 30th, 2021
638
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int, int> pii;
  5. typedef tuple<int, int, int, int, int, int> tppp;
  6.  
  7. const int N = 200;
  8.  
  9. pii dir[5] = {pii(0, 0), pii(1, 0), pii(0, 1), pii(-1, 0), pii(0, -1)};
  10. char board[N + 1][N + 2];
  11. bool visited[N + 1][N + 1][6][1 << 7];
  12. int row, col;
  13.  
  14. bool isInBoard(int r, int c){
  15.     return r >= 1 && r <= row && c >= 1 && c <= col;
  16. }
  17.  
  18. int main(){
  19.  
  20.     pii st;
  21.     scanf("%d%d", &row, &col);
  22.     int gemCnt = 0;
  23.     queue<tppp> que;
  24.     for(int i = 1; i <= row; ++i){
  25.         for(int j = 1; j <= col; ++j){
  26.             scanf(" %c", &board[i][j]);
  27.             if(board[i][j] == 'S'){
  28.                 visited[i][j][1][0] = true;
  29.                 que.emplace(i, j, 1, 0, 0, 0);
  30.                 board[i][j] = '.';
  31.             } else if(board[i][j] == 'G'){
  32.                 board[i][j] = gemCnt + 'A';
  33.                 ++gemCnt;
  34.             }
  35.         }
  36.     }
  37.     while(!que.empty()){
  38.         int ur = get<0>(que.front());
  39.         int uc = get<1>(que.front());
  40.         int us = get<2>(que.front());
  41.         int ug = get<3>(que.front());
  42.         int gemCnt = get<4>(que.front());
  43.         int dist = get<5>(que.front());
  44.         que.pop();
  45.         if(gemCnt == 7){
  46.             cout << dist;
  47.             return 0;
  48.         }
  49.         int vs = (us + 1) % 6;
  50.         for(int d = 0; d < 5; ++d){
  51.             int vr = ur + dir[d].first;
  52.             int vc = uc + dir[d].second;
  53.             if(!isInBoard(vr, vc) || board[vr][vc] == '#'){
  54.                 continue;
  55.             }
  56.             int vg = ug;
  57.             int vCnt = gemCnt;
  58.             bool req = true;
  59.             if(board[vr][vc] >= '1' && board[vr][vc] <= '6'){
  60.                 int reqGem = board[vr][vc] - '0';
  61.                 req = (reqGem <= gemCnt) || (reqGem % 6 == vs);
  62.             } else if(board[vr][vc] >= 'A' && board[vr][vc] <= 'G'){
  63.                 if((ug & (1 << (board[vr][vc] - 'A'))) == 0){
  64.                     vg = (ug | (1 << (board[vr][vc] - 'A')));
  65.                     ++vCnt;
  66.                 }
  67.             }
  68.             if(req && !visited[vr][vc][vs][vg]){
  69.                 visited[vr][vc][vs][vg] = true;
  70.                 que.emplace(vr, vc, vs, vg, vCnt, dist + 1);
  71.             }
  72.         }
  73.     }
  74.     cout << "-1";
  75.  
  76.     return 0;
  77. }
  78.  
RAW Paste Data