BOJ 19537 - 전투 시뮬레이션

BOJ 19537 - 전투 시뮬레이션

간만에 깡구현스러운 느낌이 나는 문제이다.

우선 $r_i$가 $-1$이 아니라면 항상 $1$이상이고 $1 \le m \le 20$ 임을 관찰하면 매 시도마다 다익스트라를 돌려도 최대 $200$개 정도의 칸에 대해서만 진행이 됨을 알 수 있다.

그 이후는 문제의 조건을 잘 읽고 구현해야 한다.

dist 배열같은 경우는 그냥 memset을 활용하면 매번 초기화시켜도 시간안에 돌아간다.

struct Unit {  
   int m, t, y, x;  
};  
const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};  
  
int enemy[501][501][2], dist[501][501];  
  
void solve() {  
   int N, Y, X;  
   cin >> N >> Y >> X;  
   vvi b(Y, vi(X));  
   fv2(b);  
   vi r(N);  
   fv(r);  
   for (auto &b1: b) for (auto &i: b1) i = r[i - 1];  
   int M;  
   cin >> M;  
   vector<Unit> units;  
   vector<vvi> cnt(Y, vvi(X, vi(2)));  
  
   auto near = [&](int y, int x) {  
      vector<pi> ret;  
      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) {  
            ret.pb({ny, nx});  
         }  
      }  
      return ret;  
   };  
  
   for (int i = 0; i < M; i++) {  
      int m, t, y, x;  
      cin >> m >> t >> y >> x;  
      units.pb({m, t, y, x});  
      cnt[y][x][t] = 1;  
  
      for (auto &[y, x]: near(y, x)) enemy[y][x][t]++;  
   }  
   int k;  
   cin >> k;  
  
   while (k--) {  
      int i, ey, ex;  
      cin >> i >> ey >> ex, i--;  
  
      // 갈 수 없는 곳  
      if (b[ey][ex] == -1) continue;  
      // 이미 그 위치에 유닛이 있음  
      if (cnt[ey][ex][0] + cnt[ey][ex][1]) continue;  
  
      int sy = units[i].y, sx = units[i].x;  
  
      priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;  
      pq.push({0, sy, sx});  
      memset(dist, 0x3f3f3f3f, sizeof dist);  
      dist[sy][sx] = 0;  
      int t = units[i].t, m = units[i].m;  
  
      int reachable = 0;  
      while (sz(pq)) {  
         auto [cur_d, y, x] = pq.top();  
         pq.pop();  
         if (dist[y][x] < cur_d) continue;  
  
         if (y == ey && x == ex) {  
            reachable = 1;  
            break;  
         }  
         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 (b[ny][nx] == -1) continue;  
               if (cur_d + b[ny][nx] > m) continue;  
               if (cnt[ny][nx][1 - t]) continue;  
               if (mp(ey, ex) != mp(ny, nx) && enemy[ny][nx][1 - t]) continue;  
  
               if (dist[ny][nx] > cur_d + b[ny][nx]) {  
                  pq.push({dist[ny][nx] = cur_d + b[ny][nx], ny, nx});  
               }  
            }  
         }  
      }  
      if (reachable) {  
         for (auto &[y, x]: near(units[i].y, units[i].x)) enemy[y][x][t]--;  
         cnt[units[i].y][units[i].x][t]--;  
         cnt[ey][ex][t]++;  
         units[i].y = ey;  
         units[i].x = ex;  
         for (auto &[y, x]: near(units[i].y, units[i].x)) enemy[y][x][t]++;  
      }  
   }  
   for (int i = 0; i < M; i++) {  
      cout << units[i].y << ' ' << units[i].x << endl;  
   }  
}