先预处理每个格子的最早摧毁时间，再在“到达时间必须严格早于摧毁时间”的约束下做 BFS。
OJ: luogu
题目 ID: P2895
难度:普及/提高-
标签:bfs最短路图论坐标搜索思维python
日期: 2026-06-19 08:30
题意
平面第一象限上，Bessie 从 (0,0) 出发，每秒可以向上、下、左、右走一格。
有 M 颗流星，第 i 颗会在时间 Ti 砸到 (Xi, Yi)，并同时摧毁：
(Xi, Yi)自己；- 上下左右四个相邻格子。
如果一个格子会在时间 t 被摧毁，那么 Bessie 在时间 t 以及更晚都不能站在这个格子上。
要求求出：Bessie 最早什么时候能到达一个永远不会被摧毁的安全点；如果办不到，输出 -1。
思路
最直接的办法，是把状态写成 (x,y,t)，按时间一秒一秒搜索。
这个版本最贴近题意：
cpp
#include <bits/stdc++.h>
using namespace std;
const int LIM = 25;
const int INF = 0x3f3f3f3f;
int m;
int danger_time[LIM][LIM];
bool vis[LIM][LIM][80];
int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, 1, -1};
struct Node {
int x;
int y;
int t;
};
bool in_board(int x, int y) {
return x >= 0 && x < LIM && y >= 0 && y < LIM;
}
int solve() {
if (danger_time[0][0] == 0) {
return -1;
}
memset(vis, 0, sizeof(vis));
queue<Node> q;
q.push((Node){0, 0, 0});
vis[0][0][0] = true;
// 小数据暴力：把时间显式写进状态，逐秒搜索。
while (!q.empty()) {
Node u = q.front();
q.pop();
if (danger_time[u.x][u.y] == INF) {
return u.t;
}
if (u.t >= 75) {
continue;
}
for (int i = 1; i <= 4; i++) {
int nx = u.x + dx[i];
int ny = u.y + dy[i];
int nt = u.t + 1;
if (!in_board(nx, ny)) {
continue;
}
if (nt >= danger_time[nx][ny]) {
continue;
}
if (vis[nx][ny][nt]) {
continue;
}
vis[nx][ny][nt] = true;
q.push((Node){nx, ny, nt});
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m;
for (int i = 0; i < LIM; i++) {
for (int j = 0; j < LIM; j++) {
danger_time[i][j] = INF;
}
}
for (int i = 1; i <= m; i++) {
int x, y, t;
cin >> x >> y >> t;
for (int j = 0; j <= 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if (!in_board(nx, ny)) {
continue;
}
danger_time[nx][ny] = min(danger_time[nx][ny], t);
}
}
cout << solve() << '\n';
return 0;
}但这里其实有一个很重要的单调性：
同一个格子，越早到越好
流星只会让格子越来越危险，不会让它重新变安全。
所以对于同一个格子：
- 如果已经能在时间
t到达， - 那么以后更晚时间再到达它，不会更优。
这意味着我们完全没必要把“时间”完整展开成三维大状态，只要记录每个格子的最早到达时间即可。
先预处理最早摧毁时间
设 danger_time[x][y] 表示格子 (x,y) 最早什么时候会被流星摧毁。
每颗流星会影响 5 个格子，所以读入时直接更新这 5 个位置的最小摧毁时间。
如果某格子从来不会被摧毁，就把它记成无穷大。
在时间约束下做 BFS
从 (0,0) 出发做普通 BFS。
当前在 (x,y)，时间是 t，若要走到相邻格子 (nx,ny)，到达时间就是 t+1。
只有在下面这个条件成立时，才能进入它：
t + 1 < danger_time[nx][ny]
这里必须是严格小于，因为题目明确说：在一个格子被摧毁的那个时刻以及之后，都不能站在上面。
什么时候可以结束
如果 BFS 到达了某个 danger_time 为无穷大的格子，说明这个格子永远安全。
而 BFS 又保证是按时间从小到大扩展的，所以这一定是最早到达安全点的时间，可以立刻输出答案。
Python 知识
danger字典只保存会被摧毁的坐标；不在字典中的点天然表示永久安全，不必开固定大小网格。danger.get(point, inf)对从未受影响的坐标返回无穷大。- 坐标使用元组，可直接作为
dict和set的键；队列状态用(*point,time)解包构造。 /home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：字典、集合与deque的选择。/home/rainboy/mycode/hugo-blog/content/program_language/python/bfs_shortest.md：隐式状态图最短路。
代码 python
python
from collections import deque
from math import inf
danger = {}
affected = ((0, 0), (1, 0), (-1, 0), (0, 1), (0, -1))
for _ in range(int(input())):
x, y, time = map(int, input().split())
for dx, dy in affected:
point = x + dx, y + dy
if point[0] >= 0 and point[1] >= 0:
danger[point] = min(danger.get(point, inf), time)
queue = deque([] if danger.get((0, 0)) == 0 else [(0, 0, 0)])
visited = {(0, 0)}
answer = -1
while queue:
x, y, time = queue.popleft()
if (x, y) not in danger:
answer = time
break
next_time = time + 1
for dx, dy in affected[1:]:
point = x + dx, y + dy
if point[0] < 0 or point[1] < 0 or point in visited:
continue
if next_time >= danger.get(point, inf):
continue
visited.add(point)
queue.append((*point, next_time))
print(answer)代码 c++
cpp
/**
* 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: 2025-11-28 15:41
* update_at: 2025-11-28 15:41
*/
/*
* 题目：[USACO08FEB] Meteor Shower S (luogu 2895)
* 核心思路：
* 1. 先处理所有流星，计算出每个格子最早被摧毁的时间 danger_time。
* 2. BFS 从 (0,0) 出发，每次移动到达格子 (nx,ny) 的时间为 t+1。
* 3. 只有 t+1 < danger_time[nx][ny] 才能进入该格子（严格小于，因为摧毁时刻即不可站）。
* 4. 第一次到达 danger_time 为无穷的格子就是安全点，直接返回时间。
* 5. 若队列为空还没找到，返回 -1。
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000; // 流星坐标最大 300，安全边界取 1000 确保能绕行
const int INF = 0x3f3f3f3f;
int danger_time[MAXN][MAXN]; // 每个格子最早被摧毁的时间，INF 表示永不摧毁
bool vis[MAXN][MAXN]; // BFS 是否已访问
// 移动方向：不动、右、左、上、下（不动用于处理流星影响的 5 个格子）
int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, 1, -1};
struct Point {
int x, y, step;
};
bool in_board(int x, int y) {
return x >= 0 && x < MAXN && y >= 0 && y < MAXN;
}
int bfs() {
// 起点在时间 0 就被摧毁，无法出发
if (danger_time[0][0] == 0)
return -1;
memset(vis, 0, sizeof(vis));
queue<Point> q;
vis[0][0] = true;
q.push({0, 0, 0});
while (!q.empty()) {
Point u = q.front(); q.pop();
// 当前格子永不摧毁，已到达安全点
if (danger_time[u.x][u.y] == INF)
return u.step;
for (int i = 1; i <= 4; i++) {
int nx = u.x + dx[i];
int ny = u.y + dy[i];
int nt = u.step + 1;
if (!in_board(nx, ny)) continue;
if (vis[nx][ny]) continue;
if (nt >= danger_time[nx][ny]) continue;
vis[nx][ny] = true;
q.push({nx, ny, nt});
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 初始化 danger_time 为 INF
for (int i = 0; i < MAXN; i++)
for (int j = 0; j < MAXN; j++)
danger_time[i][j] = INF;
int m;
cin >> m;
for (int i = 1; i <= m; i++) {
int x, y, t;
cin >> x >> y >> t;
// 每颗流星摧毁自身及上下左右共 5 个格子
for (int k = 0; k < 5; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (!in_board(nx, ny)) continue;
danger_time[nx][ny] = min(danger_time[nx][ny], t);
}
}
cout << bfs() << '\n';
return 0;
}复杂度
- 时间复杂度：
，其中 V是 BFS 实际访问的坐标数 - 空间复杂度：
总结
这题的核心不是普通 BFS 本身，而是先抽象出“每个格子的最早死亡时间”。
一旦有了这个时间上限，剩下的就是一个带可进入条件的最短路搜索：
第一次到达某格子的时间最优，而第一次到达任意永远安全格子的时间就是答案。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
