BOJ 25919 - Lost Edge

image.png

단순한 BFS를 여러번 돌리는 문제지만, 쉽게 생각하지 않고 뭔가 시간초과가 날거같아서 좀 걸렸다.

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};
void solve() {
   int Y, X, L, E, K, sy, sx, ey, ex;
   cin >> Y >> X >> L >> E >> K;
   vvi b(Y, vi(X));
   fv2(b);
   for (int y = 0; y < Y; y++)
      for (int x = 0; x < X; x++) {
         if (b[y][x] == -3)
            sy = y, sx = x;
         if (b[y][x] == -2)
            ey = y, ex = x;
      }
   debug(sy, sx);
   auto kill = [&](int e) {
      E += e;
      while (E >= L) {
         E -= L;
         L++;
      }
   };
   while (1) {
      //print(b);
      queue<pi> q;
      q.push({sy, sx});
      vector<bitset<100>> vis(100);
      vis[sy][sx] = 1;
      int any_improved = 0;
      debug(L, E);
      while (sz(q)) {
         auto [y, x] = q.front();
         q.pop();
         for (int d = 0; d < 4; d++) {
            int ny = y + dy[d], nx = x + dx[d];
            if (ny >= 0 && ny < Y && nx >= 0 && nx < X) {
               if (vis[ny][nx]) continue;
               if (b[ny][nx] == -1) continue;
               else if (b[ny][nx] == -2) {
                  if (L >= K) {
                     cout << 'O';
                     return;
                  }
               } else if (L > b[ny][nx]) {

                  if (b[ny][nx] > 0) {
                     any_improved = 1;
                     kill(b[ny][nx]);
                     b[ny][nx] = 0;
                     vis[ny][nx] = 1;
                     q.push({ny, nx});
                  } else {
                     vis[ny][nx] = 1;
                     q.push({ny, nx});
                  }
               }
            }
         }
      }
      out:;
      if (!any_improved)break;
   }
   cout << 'X';
}

Tags:

Categories:

Updated:

Comments