BOJ 11451 - 팩맨

BOJ 11451 - 팩맨

지문이 거지같다. 어떻게 풀었는지 잘 기억은 안난다.

사실 그냥 단순 BFS이고 힌트는 유령이든 뭐든 신경쓰지 않고 구해주면 된다는 점이다.

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};

int dist[51][51][51][51];

array<int, 5> post[51][51][51][51];

void solve() {
   memset(dist, 0x3f3f3f3f, sizeof dist);
   int Y, X;
   cin >> Y >> X;
   vs b(Y);
   fv(b);
   int sy1 = -1, sx1, sy2, sx2;
   for (int y = 0; y < Y; y++) {
      for (int x = 0; x < X; x++) {
         if (b[y][x] == 'P') {
            if (sy1 == -1) sy1 = y, sx1 = x;
            else sy2 = y, sx2 = x;
         }
      }
   }
   dist[sy1][sx1][sy2][sx2] = 0;
   queue<array<int, 4>> q;
   q.push({sy1, sx1, sy2, sx2});

   while (sz(q)) {
      auto [y1, x1, y2, x2] = q.front();
      q.pop();
      for (int d1 = 0; d1 < 4; d1++) {
         int ny1 = md(Y, y1 + dy[d1]);
         int nx1 = md(X, x1 + dx[d1]);
         int ny2 = md(Y, y2 + dy[d1]);
         int nx2 = md(X, x2 + dx[d1]);

         if (b[ny1][nx1] == 'X') ny1 = md(Y, ny1 - dy[d1]), nx1 = md(X, nx1 - dx[d1]);
         if (b[ny2][nx2] == 'X') ny2 = md(Y, ny2 - dy[d1]), nx2 = md(X, nx2 - dx[d1]);

         if (y1 == ny1 && x1 == nx1 && y2 == ny2 && x2 == nx2) continue;
         int heat = b[ny1][nx1] == 'G' || b[ny2][nx2] == 'G';

         if (heat) continue;

         int &d = dist[ny1][nx1][ny2][nx2];
         if (d > 1 + dist[y1][x1][y2][x2]) {
            d = dist[y1][x1][y2][x2] + 1;
            q.push({ny1, nx1, ny2, nx2});
            post[ny1][nx1][ny2][nx2] = {y1, x1, y2, x2, d1};
         }
      }
   }
   int mn_dist = 0x3f3f3f3f;
   for (int y = 0; y < Y; y++) {
      for (int x = 0; x < X; x++) {
         if (dist[y][x][y][x] < mn_dist && b[y][x] != 'X' && b[y][x] != 'G') {
            mn_dist = dist[y][x][y][x];
         }
      }
   }
   if (mn_dist == 0x3f3f3f3f) cout << "IMPOSSIBLE\n";
   else {
      for (int y = 0; y < Y; y++) {
         for (int x = 0; x < X; x++) {
            if (dist[y][x][y][x] == mn_dist) {
               mn_dist = dist[y][x][y][x];

               debug(y, x);
               cout << mn_dist << ' ';
               string ans;
               int y1 = y, y2 = y, x1 = x, x2 = x;

               while (1) {
                  auto [ny1, nx1, ny2, nx2, dir] = post[y1][x1][y2][x2];
                  ans += dir == 0 ? 'N' : dir == 1 ? 'E' : dir == 2 ? 'S' : 'W';
                  y1 = ny1;
                  y2 = ny2;
                  x1 = nx1;
                  x2 = nx2;
                  debug(y1, x1, y2, x2);
                  bool same_pos = mp(y1, x1) == mp(sy1, sx1) && mp(y2, x2) == mp(sy2, sx2)
                     || mp(y2, x2) == mp(sy1, sx1) && mp(y1, x1) == mp(sy2, sx2);
                  if (same_pos) break;
               }
               reverse(all(ans));
               cout << ans << endl;
               return;
            }
         }
      }
   }
}