[USACO08FEB] Meteor Shower S

形式化题目

在第一象限的网格平面上，Bessie 从 $(0,0)$ 出发，时间为 $0$ ，每秒可以走到上下左右相邻的一个格子，坐标不能为负。

给定 $M$ 颗流星，第 $i$ 颗在时间 $T_i$ 摧毁点 $(X_i, Y_i)$ 以及它的四个四邻格。摧毁之后该点永远不可站，且站在上面的时间必须严格早于摧毁时间。

求到达任意一个永远不会被摧毁的格子的最早时间；若无法到达，输出 $-1$ 。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-13 13:22
 * update_at: 2026-08-13 13:22
 */
// brute.cpp：小数据暴力解，把时间显式写进状态 (x,y,t)，逐秒搜索。
// 它不利用「第一次到达某个格子就是最早到达」的性质，同一个格子可能被
// 多次访问，状态数多，只适合小数据验证，用来和 main.cpp 对拍。

#include <bits/stdc++.h>
using namespace std;

const int LIM = 40;         // 小数据地图范围 0..39，远大于 gen.py 的流星影响区域
const int MAXT = LIM * LIM; // 时间上限：最短路经过的格子互不相同，长度不可能超过格点总数
const int INF = 0x3f3f3f3f;

int danger[LIM][LIM];        // 每个格子最早被摧毁的时间
bool vis[LIM][LIM][MAXT];    // 状态 (x,y,t) 是否访问过

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

struct Node {
    int x, y, t; // 位置与到达时间
};

int solve() {
    // 起点在时间 0 就被摧毁，一开始就无路可走
    if (danger[0][0] == 0)
        return -1;

    memset(vis, 0, sizeof(vis));
    queue<Node> q;
    q.push({0, 0, 0});
    vis[0][0][0] = true;

    while (!q.empty()) {
        Node u = q.front();
        q.pop();

        // 到达了永远不会被摧毁的格子，当前时间就是答案
        if (danger[u.x][u.y] == INF)
            return u.t;

        // 超过时间上限，认为这个分支不可能通向答案
        if (u.t + 1 >= MAXT)
            continue;

        for (int i = 0; i < 4; i++) {
            int nx = u.x + dx[i];
            int ny = u.y + dy[i];
            if (nx < 0 || nx >= LIM || ny < 0 || ny >= LIM)
                continue;
            if (u.t + 1 >= danger[nx][ny]) // 到达时间必须严格早于摧毁时间
                continue;
            if (vis[nx][ny][u.t + 1])
                continue;
            vis[nx][ny][u.t + 1] = true;
            q.push({nx, ny, u.t + 1});
        }
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 初始化所有格子为永不摧毁
    for (int i = 0; i < LIM; i++)
        for (int j = 0; j < LIM; j++)
            danger[i][j] = INF;

    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        // 流星摧毁自己与四邻格，取所有流星中最早的摧毁时间
        danger[x][y] = min(danger[x][y], t);
        if (x + 1 < LIM) danger[x + 1][y] = min(danger[x + 1][y], t);
        if (x - 1 >= 0) danger[x - 1][y] = min(danger[x - 1][y], t);
        if (y + 1 < LIM) danger[x][y + 1] = min(danger[x][y + 1], t);
        if (y - 1 >= 0) danger[x][y - 1] = min(danger[x][y - 1], t);
    }

    cout << solve() << '\n';
    return 0;
}

brute.cpp 把时间原样展开成状态 (x, y, t)：vis[x][y][t] 记录访问，同一个格子在不同时间可以反复入队，t 超过上限就剪掉。它是"逐秒模拟"的最直接写法，但时间维把状态放大了上千倍，满分数据（坐标到 300、时间到 1000）完全不可行。

关键观察是同一个格子越早到达越好：流星只会让格子越来越危险，永远不会让它重新变安全。所以只要记录每个格子最早的到达时间，而网格图边权全为 1，BFS 第一次访问一个格子时就是最早到达时间——时间维是冗余的。

于是做法分成两步：

预处理最早摧毁时间。设 danger[x][y] 为格子 (x, y) 最早被摧毁的时间，从未被影响的格子记无穷大。每颗流星只影响 5 个格子，读入时直接对这 5 个位置取 min。
带约束的 BFS。从 (0, 0) 出发，走到相邻格子 (nx, ny) 的到达时间是 t + 1，只有满足 t + 1 < danger[nx][ny]（严格小于，摧毁时刻不可站）才允许进入。BFS 第一次遇到 danger == INF 的格子，就输出当前时间；队列耗尽则输出 -1。

以样例的摧毁时间网格为例（. 表示永远安全，表格是 $x$ 行、 $y$ 列）：

text

1
2
3
4
5        y=0  y=1  y=2  y=3  y=4
x=0:    2    2    5    5    5
x=1:    2    2    2    5    .
x=2:    2    2    2    .    .
x=3:    .    2    .    .    .

注意 x=1..2, y=0..2 这片区域摧毁时间是 2，从 (0,0) 出发最早也要 2 秒才可能到达，永远赶不上；唯一出路是沿 (0,1)->(0,2)->(0,3)->(1,3)->(1,4) 绕行，第 5 秒到达永远安全的 (1,4)，答案正是 5。

实现上有三个容易错的地方：

地图范围：流星坐标最大 300，受影响格子最大到 301；若危险区把 [0,301]^2 全部覆盖，逃逸必须踩上坐标 302 的第一圈安全格，所以数组要开 305（下标 0…304）；
起点即死：若 danger[0][0] == 0，Bessie 在时间 0 就被摧毁，直接输出 -1；
严格小于：t + 1 >= danger[nx][ny] 一律不能进，包括恰好相等的情况。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-13 13:22
 * update_at: 2026-08-13 13:22
 */
/*
 * 题目：[USACO08FEB] Meteor Shower S（洛谷 P2895）
 * 核心思路：
 * 1. 每颗流星在时间 t 摧毁 (x,y) 及上下左右四个相邻格子，
 *    预处理出每个格子最早的摧毁时间 danger。
 * 2. 从 (0,0) 做 BFS，走到新格子 (nx,ny) 的到达时间为 t+1，
 *    只有 t+1 < danger[nx][ny] 才能进入（严格小于，摧毁时刻即不可站）。
 * 3. 第一次到达永远不会被摧毁的格子（danger 为 INF）就是答案；
 *    队列耗尽还没找到则输出 -1。
 */

#include <bits/stdc++.h>
using namespace std;

// 流星坐标最大 300，受影响格子最大到 301，开 0..304 保证能逃出危险区
const int MAXN = 305;
const int INF = 0x3f3f3f3f;

int danger[MAXN][MAXN]; // danger[x][y]：格子 (x,y) 最早被摧毁的时间，INF 表示永远安全
bool vis[MAXN][MAXN];   // BFS 访问标记

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

struct Node {
    int x, y, t; // 当前位置与到达时间
};

int bfs() {
    // 起点在时间 0 就被摧毁，一开始就无路可走
    if (danger[0][0] == 0)
        return -1;

    memset(vis, 0, sizeof(vis));
    queue<Node> q;
    q.push({0, 0, 0});
    vis[0][0] = true;

    while (!q.empty()) {
        Node u = q.front();
        q.pop();

        // 到达了永远不会被摧毁的格子：BFS 按时间递增扩展，第一次到达即最早
        if (danger[u.x][u.y] == INF)
            return u.t;

        for (int i = 0; i < 4; i++) {
            int nx = u.x + dx[i];
            int ny = u.y + dy[i];
            if (nx < 0 || nx >= MAXN || ny < 0 || ny >= MAXN)
                continue;
            if (vis[nx][ny])
                continue;
            if (u.t + 1 >= danger[nx][ny]) // 到达时间必须严格早于摧毁时间
                continue;
            vis[nx][ny] = true;
            q.push({nx, ny, u.t + 1});
        }
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 初始化所有格子为永不摧毁
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            danger[i][j] = INF;

    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        // 流星摧毁自己与四邻格，取所有流星中最早的摧毁时间
        danger[x][y] = min(danger[x][y], t);
        if (x + 1 < MAXN) danger[x + 1][y] = min(danger[x + 1][y], t);
        if (x - 1 >= 0) danger[x - 1][y] = min(danger[x - 1][y], t);
        if (y + 1 < MAXN) danger[x][y + 1] = min(danger[x][y + 1], t);
        if (y - 1 >= 0) danger[x][y - 1] = min(danger[x][y - 1], t);
    }

    cout << bfs() << '\n';
    return 0;
}

复杂度

时间：预处理 $O(M)$ ，BFS 每个格子最多入队一次， $O(MAXN^2)$ （ $MAXN = 305$ ），总复杂度 $O(M + MAXN^2)$ 。
空间：danger 与 vis 两个 $305 \times 305$ 数组加一个队列， $O(MAXN^2)$ 。

总结

这道题的套路是"先把所有时间信息预处理成格子的属性，再做最短路搜索"：摧毁时间被压缩成 danger[x][y] 上的一个静态约束，剩下的就是一次带进入条件的 BFS。"同一个格子越早到越好"保证了 BFS 第一次访问即最优，于是时间维可以整个丢掉。网格图上带"可进入时刻限制"的搜索题（如涨潮、起火扩散类问题）都可以套这个模型；brute.cpp 的"显式时间维 BFS"则是对拍和验证思路的好基准。BFS 的遍历与队列结构可参考 rbook 的《图的遍历》。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20流星输入 (x, y, t)
    |
    | 每颗流星摧毁自己 + 四邻，共 5 个格子
    v
预处理 danger[x][y]：每个格子最早被摧毁时间
  多颗流星取 min，从未被影响记 INF（永远安全）
    |
    | 危险只会增加：同一个格子越早到越好
    v
关键观察：边权全为 1 的网格图，BFS 第一次访问 = 最早到达
    | 时间维冗余：vis[x][y] 代替 vis[x][y][t]
    v
BFS（main.cpp）
  从 (0,0) 出发，时间 0；danger[0][0] == 0 直接 -1
  进入 (nx,ny) 的条件：t + 1 < danger[nx][ny]（严格小于）
  队首 danger == INF：输出 t，即答案
  队列耗尽：输出 -1
    |
    v
复杂度 O(M + 305^2)，空间 O(305^2)

图中三条主线分别对应"信息如何压缩"“优化依据是什么”“正式解如何利用它”。danger 预处理把题目的全部时间信息固化到格子上，BFS 不再需要任何时间维状态；第一个弹出队列的安全格必然时间最小，这就是答案。