把所有感染源同时作为 BFS 起点，一次多源 BFS 预处理整张图，再直接回答每个领主的感染时间。
OJ: luogu
题目 ID: P1332
难度:普及-
标签:bfs最短路图论网格多源bfs
日期: 2026-06-19 08:26
题意
有一个 n × m 的方阵，里面的人会感染瘟疫。
一开始给出 a 个感染源，它们在第 0 小时就已经被感染。
之后每过 1 小时，瘟疫会向上、下、左、右扩散一格。
现在还给出 b 个领主的位置，要求输出每个领主在第几小时会被感染。
样例里两个感染源分别在 (1,1) 和 (5,4)，所以整张图的感染时间，其实就是每个格子到这两个源点的四联通最短距离的较小值。
思路
最直观的办法，是把感染过程一小时一小时模拟：
- 第
0小时先有一批感染源； - 第
1小时这些点向外扩一层； - 第
2小时再继续扩。
这个版本很容易理解：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 35;
int n, m, a, b;
int dista[MAXN][MAXN];
bool infected[MAXN][MAXN];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
struct Node {
int x;
int y;
};
bool in_board(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> a >> b;
vector<Node> cur;
memset(dista, -1, sizeof(dista));
for (int i = 1; i <= a; i++) {
int x, y;
cin >> x >> y;
if (!infected[x][y]) {
infected[x][y] = true;
dista[x][y] = 0;
cur.push_back((Node){x, y});
}
}
// 朴素模拟：按“第 0 小时、第 1 小时……”一层一层扩散瘟疫。
int hour = 0;
while (!cur.empty()) {
vector<Node> nxt;
for (int idx = 0; idx < (int) cur.size(); idx++) {
int x = cur[idx].x;
int y = cur[idx].y;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!in_board(nx, ny)) {
continue;
}
if (infected[nx][ny]) {
continue;
}
infected[nx][ny] = true;
dista[nx][ny] = hour + 1;
nxt.push_back((Node){nx, ny});
}
}
cur.swap(nxt);
hour++;
}
for (int i = 1; i <= b; i++) {
int x, y;
cin >> x >> y;
cout << dista[x][y] << '\n';
}
return 0;
}但如果对每个领主单独去搜最近感染源，会有大量重复工作。
同时扩散 = 多源 BFS
题目里所有感染源是“同时开始扩散”的。
这正好对应图论里的多源 BFS：
- 把所有感染源一起作为第
0层； - 同时入队；
- 像普通 BFS 一样往外一层层扩展。
谁先到达某个格子，谁就决定了这个格子的最早感染时间。
为什么这样是对的
因为每次传播到相邻格子的代价都相同，都是 1 小时。
所以这本质上就是无权图最短路问题。
在无权图里，BFS 第一次访问到某个点时，得到的距离一定是最短的。
这里的距离，正好就是感染时间。
正式做法
- 建一个
dista[x][y]，表示格子(x,y)最早在第几小时感染； - 所有感染源的距离初始化为
0，并全部入队； - 做一次多源 BFS，把整张图的感染时间全部求出来；
- 之后每个领主查询，直接输出它所在格子的距离。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
int n, m, a, b;
int dista[MAXN][MAXN];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
struct Node {
int x;
int y;
};
bool in_board(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> a >> b;
memset(dista, -1, sizeof(dista));
queue<Node> q;
for (int i = 1; i <= a; i++) {
int x, y;
cin >> x >> y;
if (dista[x][y] == -1) {
dista[x][y] = 0;
q.push((Node){x, y});
}
}
while (!q.empty()) {
Node u = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = u.x + dx[i];
int ny = u.y + dy[i];
if (!in_board(nx, ny)) {
continue;
}
if (dista[nx][ny] != -1) {
continue;
}
dista[nx][ny] = dista[u.x][u.y] + 1;
q.push((Node){nx, ny});
}
}
for (int i = 1; i <= b; i++) {
int x, y;
cin >> x >> y;
cout << dista[x][y] << '\n';
}
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题的关键不在搜索本身，而在于识别出“多个源点同时扩散”这个结构。
一旦看到这点，就应该直接想到多源 BFS：一次预处理整张图，然后所有查询都只要查表。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
