写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：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 #include #include #include using namespace std; typedef pair 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 ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
