Advertisement
Josif_tepe

Untitled

Apr 16th, 2022
682
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.16 KB | None
  1. class VampiresWalk
  2. {
  3.   public:
  4.     bool visited[22][22][6][1 << 8];
  5.     int getMinTime( vector<string> maze )
  6.     {
  7.         int n = maze.size();
  8.         int m = maze[0].size();
  9.        
  10.         int si, sj;
  11.         int prey = 0;
  12.         for(int i = 0; i < n; i++) {
  13.             for(int j = 0; j < m; j++) {
  14.                 if(maze[i][j] == 'V') {
  15.                     si = i;
  16.                     sj = j;
  17.                 }
  18.                 if(maze[i][j] == 'K') {
  19.                     maze[i][j] = (prey + '0');
  20.                     prey++;
  21.                 }
  22.             }
  23.         }
  24.         memset(visited, false, sizeof visited);
  25.         queue<int> q;
  26.         q.push(si);
  27.         q.push(sj);
  28.         q.push(5);
  29.         q.push(0);
  30.         q.push(0);
  31.         visited[si][sj][5][0] = true;
  32.         int di[] = {-1, 1, 0, 0};
  33.         int dj[] = {0, 0, -1, 1};
  34.         while(!q.empty()) {
  35.             int ci = q.front(); q.pop();
  36.             int cj = q.front(); q.pop();
  37.             int layers = q.front(); q.pop();
  38.             int bitmask = q.front(); q.pop();
  39.             int dist = q.front(); q.pop();
  40.            
  41.             if(bitmask == (1 << prey) - 1) {
  42.                 return dist;
  43.             }
  44.             for(int i = 0; i < 4; i++) {
  45.                 int ti = ci + di[i];
  46.                 int tj = cj + dj[i];
  47.                
  48.                 if(ti >= 0 and tj >= 0 and ti < n and tj < m) {
  49.                     if(maze[ti][tj] == '.' and !visited[ti][tj][layers][bitmask]) {
  50.                         q.push(ti);
  51.                         q.push(tj);
  52.                         q.push(layers);
  53.                         q.push(bitmask);
  54.                         q.push(dist + 1);
  55.                         visited[ti][tj][layers][bitmask] = true;
  56.                     }
  57.                     if(maze[ti][tj] == '*' and layers > 0 and !visited[ti][tj][layers - 1][bitmask]) {
  58.                         q.push(ti);
  59.                         q.push(tj);
  60.                         q.push(layers - 1);
  61.                         q.push(bitmask);
  62.                         q.push(dist + 1);
  63.                         visited[ti][tj][layers - 1][bitmask] = true;
  64.                     }
  65.                     if(maze[ti][tj] == 'P' and !visited[ti][tj][5][bitmask]) {
  66.                         q.push(ti);
  67.                         q.push(tj);
  68.                         q.push(5);
  69.                         q.push(bitmask);
  70.                         q.push(dist + 1);
  71.                         visited[ti][tj][5][bitmask] = true;
  72.                     }
  73.                     if(isdigit(maze[ti][tj])) {
  74.                         int id_prey = (maze[ti][tj] - '0');
  75.                         int new_mask = (bitmask | (1 << id_prey));
  76.                         if(!visited[ti][tj][layers][new_mask]) {
  77.                             q.push(ti);
  78.                             q.push(tj);
  79.                             q.push(layers);
  80.                             q.push(new_mask);
  81.                             q.push(dist + 1);
  82.                             visited[ti][tj][layers][new_mask] = true;
  83.                         }
  84.                     }
  85.                 }
  86.             }
  87.         }
  88.         return -1;
  89.     }
  90. };
  91.  
Advertisement
RAW Paste Data Copied
Advertisement