在标准的单源广度优先搜索中，从网格地图中的某一个确定起点出发，逐步按层向四周邻近格子扩张，用来求解网格图/棋盘中的最少移动步数（最短距离）问题。
然而，在许多实际题目中，起点的数量往往不止一个。例如：
类似这类拥有多个起始位置，且关注每个位置到“最近”起始位置的步数/距离的问题，即为多源 BFS 问题。
假设网格共有 \(R\) 行 \(C\) 列，总格数为 \(N = R \times C\)，其中起点共有 \(k\) 个。
如果对每个起点分别跑一次单源 BFS，每次单源 BFS 遍历网格的时间复杂度为 \(O(N)\)，总时间复杂度为 \(O(k \cdot N)\)。当起点数量较多，比如 \(k \apporx N\) 时，时间复杂度会暴涨至 \(O(N^2) = O((R \times C)^2)\)。在 \(1000 \times 1000\) 的网格中，计算次数高达 \(10^{12}\)。
假设网格中存在起点集合 \(S = \{s_1, s_2, \dots, s_k\}\)，可以想象存在一个虚构的“超级起点” \(S_0\)：
因为从 \(S_0\) 到各个真实起点的步数均为 \(0\)，在 BFS 初始化时：
在实际编写代码时，无需构造复杂的虚构逻辑，只需在算法启动前，将所有起点一次性全部放入 BFS 队列中，作为第 \(0\) 层（初始层）位置即可。
在一个 \(n \times m \ (1 \le n,m \le 500)\) 的网格矩阵中，分布着 \(a\) 个感染源和 \(b \ (1 \le a,b \le 10^5)\) 个领主。感染源初始感染时间为 \(0\)，从第 \(0\) 小时开始，已被感染过的格子每过 \(1\) 小时会向上下左右相邻的 \(4\) 个格子扩散瘟疫。要求计算出给定的 \(b\) 个领主分别被感染的最早时间，并按输入的顺序输出。
#include <iostream>
#include <queue>
using namespace std;
using pi = pair<int, int>;
const int N = 505;
// 定义上下左右四个方向的偏移量
const int X[] = {-1, 1, 0, 0};
const int Y[] = {0, 0, -1, 1};
int d[N][N]; // 记录每个坐标被感染的最早时间
int main()
{
int n, m, a, b;
cin >> n >> m >> a >> b;
// 初始化为 -1，表示尚未被感染
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
d[i][j] = -1;
}
}
queue<pi> q;
// 读入所有感染源并作为多源起点同时入队
while (a--) {
int x, y; cin >> x >> y;
if (d[x][y] == -1) {
d[x][y] = 0;
q.push({x, y});
}
}
// 多源广度优先搜索（BFS）
while (!q.empty()) {
pi p = q.front();
q.pop();
int x = p.first, y = p.second;
for (int i = 0; i < 4; i++) {
int nx = x + X[i], ny = y + Y[i];
// 检查边界及未访问状态
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1; // 距离加 1
q.push({nx, ny});
}
}
}
// 依次回答 b 个领主的查询
while (b--) {
int x, y; cin >> x >> y;
cout << d[x][y] << "\n";
}
return 0;
}
网格图上共 \(n \times m\) 个节点，BFS 保证每个节点最多入队和出队一次，处理四周邻居节点耗时与总节点数成正比，即 \(O(n \times m)\)。多源起点入队耗时 \(O(a)\)，最后的查询阶段回答 \(b\) 个领主的位置耗时 \(O(b)\)，总时间复杂度为 \(O(n \times m + a + b)\)。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。