写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：P1332 血色先锋队 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述：
输入格式：
第 1 行：四个整数 n，m，a，b，
表示军团矩阵有 n 行 m 列。有 a 个感染源，b 为血色敢死队中领主的数量。
接下来 a 行：每行有两个整数 x，y，表示感染源在第 x 行第 y 列。
接下来 b 行：每行有两个整数 x，y，表示领主的位置在第 x 行第 y 列。
输出格式：
第 1 至 b 行：每行一个整数，表示这个领主感染瘟疫的时间，输出顺序与输入顺序一致。
如果某个人的位置在感染源，那么他感染瘟疫的时间为 0。
输入样例：
5 4 2 3 1 1 5 4 3 3 5 3 2 4
输出样例：
3 1 3
解题思路：
根据题意，在这个血色军团组成的矩阵里，
有a个感染源，他们会向四个方向感染，
我们先将感染源的感染模拟一下，观察他的规律：
我们根据题目的给出的样例，
从感染源开始bfs，
继续往下搜索：
直到将整个血色军团都感染：
题目要求的输出的领主感染顺序，
是按照输入的顺序输出，所以，
我们有两种解决方法，
一种是用一个数组按输入顺序存储领主的感染时间，
一种是我们先用bfs搜索，然后在输入领主坐标的时候，直接输出领主的感染时间，
这里我使用的是第二种方法，
下面是代码实现：
代码：
//包好头文件 #include #include #include #include using namespace std; int n, m, a, b; typedef pair PII; const int N = 510; //记录每个位置什么时候被感染 int dist[N][N]; PII q[N * N]; int head = 0; int tail = -1; //存偏移量 int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; void bfs() { //如果队列为空就不循环 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 < 1 || a > n || b < 1 || b > m) continue; if(dist[a][b] >= 0) continue; dist[a][b] = dist[t.first][t.second] + 1; q[++tail] = {a, b}; } } } int main() { scanf("%d %d %d %d", &n, &m, &a, &b); //初始化状态数组 memset(dist, -1, sizeof(dist)); for(int i = 0; i < a; i++) { int x, y; scanf("%d %d", &x, &y); //现将所以瘟疫源都入队，就能实现几个位置同时搜索 q[++tail] = {x, y}; dist[x][y] = 0; } bfs(); //根据题目输入顺序输出领主 for(int i = 0; i < b; i++) { int x, y; scanf("%d %d", &x, &y); printf("%d\n", dist[x][y]); } return 0; }
AC ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
