【题目来源】
洛谷：[P2895 USACO08FEB] Meteor Shower S - 洛谷
【题目描述】
贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。
如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。
根据预报，一共有 \(M\) 颗流星 \((1\le M\le 50,000)\) 会坠落在农场上，其中第 \(i\) 颗流星会在时刻 \(T_i(0\le T_i\le 1000)\) 砸在坐标为 \((X_i,Y_i)(0\le X_i\le 300,0\le Y_i\le 300)\) 的格子里。流星的力量会将它所在的格子，以及周围 \(4\) 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。
贝茜在时刻 \(0\) 开始行动，她只能在第一象限中，平行于坐标轴行动，每 \(1\) 个时刻中，她能移动到相邻的（一般是 \(4\) 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 \(t\) 被流星撞击或烧焦，那么贝茜只能在 \(t\) 之前的时刻在这个格子里出现。 贝茜一开始在 \((0,0)\)。
请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 \(−1\)。
【输入】
共 \(M+1\) 行，第 \(1\) 行输入一个整数 \(M\)，接下来的 \(M\) 行每行输入三个整数分别为 \(X_i,Y_i,T_i\)。
【输出】
贝茜到达安全地点所需的最短时间，如果不可能，则为 \(−1\)。
【输入样例】
4
0 0 2
2 1 2
1 1 2
0 3 5
【输出样例】
5
【解题思路】
【算法标签】
《洛谷 P2895 流星雨》 #搜索# #广度优先搜索,BFS# #USACO# #2008#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 定义位置结构体
struct node
{int x, y; // 坐标位置int step; // 到达该位置的步数int t; // 该位置变为危险的时间（-1表示安全）int visit; // 是否已访问（1表示已访问）
} p[1005][1005]; // 定义1005x1005的网格int main()
{int m; // 危险区域的数量cin >> m;int x, y, t; // 临时变量：坐标和危险时间int tx, ty; // 临时坐标// 方向数组：上、下、左、右、原地（用于标记危险区域）int dx[5] = {-1, 1, 0, 0, 0};int dy[5] = {0, 0, -1, 1, 0};// 初始化所有位置为未访问状态memset(p, -1, sizeof(p));// 初始化每个位置的坐标for (int i = 0; i <= 1000; i++){for (int j = 0; j <= 1000; j++){p[i][j].x = i;p[i][j].y = j;}}// 输入危险区域信息for (int i = 0; i < m; i++){cin >> x >> y >> t;// 标记该位置及其四周为危险区域for (int j = 0; j <= 4; j++){tx = x + dx[j];ty = y + dy[j];if (tx < 0 || ty < 0) continue; // 超出边界则跳过// 如果该位置尚未标记危险时间，或者当前时间更早，则更新if (p[tx][ty].t == -1 || p[tx][ty].t > t){p[tx][ty].t = t;}}}// 使用BFS队列进行搜索queue<node> q;// 初始化起点(0,0)p[0][0].step = 0; // 起点步数为0p[0][0].visit = 1; // 标记为已访问q.push(p[0][0]); // 加入队列// BFS主循环while (!q.empty()){node tp = q.front();q.pop();// 尝试四个移动方向for (int i = 0; i < 4; i++){tx = tp.x + dx[i];ty = tp.y + dy[i];// 检查边界和访问状态if (tx < 0 || ty < 0 || p[tx][ty].visit == 1){continue;}// 如果找到安全区域if (p[tx][ty].t == -1){cout << tp.step + 1; // 输出当前步数+1return 0;}// 如果可以在危险时间前到达该位置if (p[tx][ty].t > tp.step + 1){p[tx][ty].visit = 1; // 标记为已访问p[tx][ty].step = tp.step + 1; // 更新步数q.push(p[tx][ty]); // 加入队列}}}// 如果没有找到安全路径cout << -1 << endl;return 0;
}
【运行结果】
4
0 0 2
2 1 2
1 1 2
0 3 5
5