目录
题目：P2895 [USACO08FEB]Meteor Shower S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：P2895 [USACO08FEB]Meteor Shower S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述：
输入格式：
共 M + 1 行，第 1 行输入一个整数 M，
接下来的 M 行每行输入三个整数分别为 Xi, Yi, Ti。
输出格式：
贝西到达安全地点所需的最短时间，如果不可能，则为 −1。
输入样例：
4
0 0 2
2 1 2
1 1 2
0 3 5输出样例：
5解题思路：
看完题目，这道题大致的意思就是：
贝茜从起点开始找安全的位置，天上的流星不断往下砸，
我们可以通过广度优先搜索帮她搜索安全的位置，
我们先通过题目给出的样例模拟一下这个过程：
贝茜从起点出发，
每次能走四个方向，
但是我们需要先将流星会砸到的地方标记出来，
如果贝茜走到被流星砸到的地方，证明那个位置是不能走的：
第一个流星砸在(2, 1)........（补丁：这里漏了,还有一颗流星是砸在(0, 0) , 不过不影响结果）
第二颗砸在(1, 1)
第三颗砸在(0, 3)
贝茜从起点出发：
继续走，如果走的是那两个地方，
就会被砸死：
这样就成功躲过流星了：
最后就返回5。
那么，根据我们刚刚模拟的思路，
下面是代码实现：
代码：
//包好头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
int n = 0;
const int N = 310;
int g[N][N];
PII q[N * N];
int dist[N][N];
int star[N][N];//存流星砸到的点
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int bfs()
{
q[0] = {0, 0};
dist[0][0] = 0;
int head = 0;
int tail = 0;
while(head <= tail)
{
auto t = q[head++];
for(int i = 0; i < 4; i++)
{
int a = t.first + dx[i];
int b = t.second + dy[i];
//控边界
if(a < 0 || b < 0) continue;
//走过的路不再走
if(dist[a][b] > 0) continue;
//如果流星已经砸了就走不了/被砸死
if(dist[t.first][t.second] + 1 >= star[a][b]) continue;
dist[a][b] = dist[t.first][t.second] + 1;
q[++tail] = {a, b};
//如果发现走到的位置没有流星砸，返回
if(star[a][b] > 1e9) return dist[a][b];
}
}
return -1;
}
int main()
{
scanf("%d", &n);
memset(star, 0x3f, sizeof(star));
while(n--)
{
int x, y, t;
scanf("%d %d %d", &x, &y, &t);
star[x][y] = min(t, star[x][y]);//流星砸到的中心点
for(int i = 0; i < 4; i++)
{
int a = dx[i] + x;
int b = dy[i] + y;
if(a < 0 || a > 300 || b < 0 || b > 300) continue;
star[a][b] = min(t, star[a][b]);//往外延伸的四个点
}
}
int res = bfs();
printf("%d", res);
return 0;
}AC ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。