YEZAELP

CUBE-153: Seven Gems

Aug 2nd, 2021
610
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 1e9;
  5. char ar[201][201];
  6. int di[] = {0, 0, 0, 1, -1}, dj[] = {0, 1, -1, 0, 0};
  7. bool vs[201][201][7][1 << 7];
  8. int n, m;
  9. struct Data{int d, i, j, c, g, cnt;};
  10.  
  11. int main(){
  12.  
  13.     scanf("%d%d", &n, &m);
  14.     queue < Data > q;
  15.  
  16.     int cnt = 0;
  17.     for(int i=1;i<=n;i++){
  18.         for(int j=1;j<=m;j++){
  19.             scanf(" %c", &ar[i][j]);
  20.             if(ar[i][j] == 'G')
  21.                 ar[i][j] = cnt + 'A', cnt ++;
  22.             else if(ar[i][j] == 'S'){
  23.                 vs[i][j][1][0] = true;
  24.                 q.push({ 0, i, j, 1, 0, 0 });
  25.                 ar[i][j] = '.';
  26.             }
  27.         }
  28.     }
  29.  
  30.     while(!q.empty()){
  31.         int ud = q.front().d;
  32.         int ui = q.front().i;
  33.         int uj = q.front().j;
  34.         int uc = q.front().c;
  35.         int ug = q.front().g;
  36.         int ucnt = q.front().cnt;
  37.         q.pop();
  38.  
  39.         for(int d=0;d<5;d++){
  40.  
  41.             int vi = ui + di[d];
  42.             int vj = uj + dj[d];
  43.             if(!(1 <= vi and vi <= n and 1 <= vj and vj <= m) or ar[vi][vj] == '#') continue;
  44.  
  45.             int vd = ud + 1;
  46.  
  47.             int vc = uc + 1;
  48.             if(vc == 7) vc = 1;
  49.  
  50.             bool check = false;
  51.             if(ar[vi][vj] == '.') check = true;
  52.             else if('1' <= ar[vi][vj] and ar[vi][vj] <= '6' and (ar[vi][vj] - '0' <= ucnt or ar[vi][vj] - '0' == vc))
  53.                 check = true;
  54.  
  55.             int vg = ug;
  56.             int vcnt = ucnt;
  57.             if('A' <= ar[vi][vj] and ar[vi][vj] <= 'G'){
  58.                 check = true;
  59.                 if((ug & (1 << (ar[vi][vj] - 'A'))) == 0){
  60.                     vcnt ++;
  61.                     if(vcnt == 7){
  62.                         printf("%d", vd);
  63.                         return 0;
  64.                     }
  65.                 }
  66.                 vg = ( ug | (1 << (ar[vi][vj] - 'A')) );
  67.             }
  68.  
  69.             if(!vs[vi][vj][vc][ug] and check){
  70.                 vs[vi][vj][vc][ug] = true;
  71.                 q.push({ vd, vi, vj, vc, vg, vcnt });
  72.             }
  73.         }
  74.     }
  75.  
  76.     printf("-1");
  77.  
  78.     return 0;
  79. }
RAW Paste Data