POJ Meteor Shower：BFS 帶時間限制的隕石閃避

問題描述

人從 (0,0) 出發，每秒可移動上下左右一格。隕石落下會摧毀落點及其四鄰格。輸入 M 隕石，每個給出 (x, y, t)：時刻 t 落在 (x, y)，摧毀該點及四鄰格。求到達任一永不被摧毀格子的最早時間，無解輸出 -1。

建模：時空 BFS

• 預處理：對每個格子記錄最早被摧毀時間 destroy[x][y]（初始 INF）。每顆隕石更新其影響的 5 格：destroy = min(destroy, t)。
• BFS 狀態 (x, y, time)。從 (0,0,0) 開始。若 destroy[x][y] == INF，說明永安全，返回 time。
• 擴展：對四個方向，新時間 nt = time + 1。若 nt >= destroy[nx][ny] 則不可進入（該時刻已被摧毀或正被摧毀）。否則入隊。
• 訪問標記 vis[x][y]：同一格子最早到達即最優，後到達無需再進隊。

代碼實現（C++）

#include <bits/stdc++.h>
using namespace std;
const int MAXC = 305;
const int INF = 0x3f3f3f3f;
int destroy_time[MAXC][MAXC];
bool vis[MAXC][MAXC];
int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};

struct State { int x, y, t; };

int bfs() {
    memset(vis, 0, sizeof(vis));
    queue<State> q;
    q.push({0,0,0}); vis[0][0] = true;
    if (destroy_time[0][0] == INF) return 0; // 起點永安全
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        for (int dir = 0; dir < 4; ++dir) {
            int nx = cur.x + dx[dir], ny = cur.y + dy[dir];
            if (nx < 0 || ny < 0) continue;
            int nt = cur.t + 1;
            if (destroy_time[nx][ny] == INF) return nt; // 到達安全區
            if (vis[nx][ny] || nt >= destroy_time[nx][ny]) continue;
            vis[nx][ny] = true;
            q.push({nx, ny, nt});
        }
    }
    return -1;
}

int main() {
    int M;
    while (~scanf("%d", &M)) {
        memset(destroy_time, 0x3f, sizeof(destroy_time));
        for (int i = 0; i < M; ++i) {
            int x, y, t; scanf("%d%d%d", &x, &y, &t);
            for (int d = 0; d < 5; ++d) {
                int nx = x + dx[d], ny = y + dy[d]; // dx[4]=dy[4]=0 含自身
                if (nx >= 0 && ny >= 0)
                    destroy_time[nx][ny] = min(destroy_time[nx][ny], t);
            }
        }
        printf("%d\n", bfs());
    }
    return 0;
}

複雜度

網格大小由隕石坐標隱含決定（≤ 300），BFS 狀態數 O(MAXC^2)，極快。