目录

写在前面：

题目：P2895 [USACO08FEB]Meteor Shower S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输出格式：

输入样例：

输出样例：

解题思路：

代码：

AC ！！！！！！！！！！

写在最后：

---

写在前面：

怎么样才能学好一个算法？

我个人认为，系统性的刷题尤为重要，

所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，

事不宜迟，我们即刻开始刷题！

题目：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 ！！！！！！！！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。