题解 | #病菌感染# BFS（广度优先搜索）
病菌感染
https://ac.nowcoder.com/acm/problem/16121
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int Sq[1005][1005];
bool visited[1005][1005];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int main() {
int n, m;
cin >> n >> m;
memset(Sq, 0, sizeof(Sq));
queue<pair<int, int>> q;
// 读入初始障碍物并加入队列
for(int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
Sq[x][y] = 2;
q.push({x, y});
}
int remaining = n * n - m;
// 多源BFS
while(!q.empty() && remaining > 0) {
auto [x, y] = q.front();
q.pop();
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && Sq[nx][ny] < 2) {
Sq[nx][ny]++;
if(Sq[nx][ny] >= 2) {
q.push({nx, ny});
remaining--;
}
}
}
}
if(remaining == 0) cout << "YES";
else cout << "NO";
return 0;
}
这段代码使用了多源BFS（广度优先搜索） 的优化思路，相比原来的暴力方法有显著改进：
核心优化思路：
- 多源BFS代替暴力遍历
· 原方法：每轮都遍历整个n×n网格，时间复杂度O(n⁴) · 优化方法：只处理当前障碍物的相邻格子，时间复杂度O(n²)
- 队列驱动的增量更新
queue<pair<int, int>> q;
// 只从障碍物位置开始扩散，而不是检查所有格子
· 只处理新变成障碍物的格子，避免重复检查 · 利用队列的FIFO特性，确保按"波次"扩散
- 实时剩余计数
int remaining = n * n - m;
// 每次新障碍物产生时递减
remaining--;
· 实时跟踪剩余可通行格子数量 · 当remaining == 0时立即终止，避免不必要的计算
- 方向数组简化代码
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
· 统一处理四个方向，代码更简洁 · 避免重复的方向判断代码
- 累积计数机制
Sq[nx][ny]++; // 累积被相邻障碍物影响的次数
if(Sq[nx][ny] >= 2) { // 达到阈值变成障碍物
q.push({nx, ny});
remaining--;
}
· 每个格子记录被相邻障碍物影响的次数 · 只有当影响次数≥2时才变成新障碍物 · 这模拟了原问题中"需要被两个以上障碍物相邻影响"的规则
算法流程对比：
原算法：
重复直到稳定：
遍历所有格子 → O(n²)
对每个障碍物更新邻居 → O(4n²)
再次遍历所有格子计数 → O(n²)
总复杂度：O(k × n²)，k可能达到O(n²)
BFS优化：
初始化队列
while(队列非空且还有剩余格子):
取出一个障碍物 → O(1)
更新4个邻居 → O(1)
如果邻居达到阈值则加入队列 → O(1)
总复杂度：O(n²)
关键优势：
- 避免空转：只处理实际会发生变化的区域
- 提前终止：一旦所有格子都变成障碍物就立即结束
- 内存友好：不需要额外的临时数组
- 逻辑清晰：BFS的自然扩散过程与问题语义高度匹配
这种优化将最坏情况下的时间复杂度从O(n⁴)降低到O(n²)，对于n=1000的情况，从10¹²操作降到10⁶操作，是百万倍的性能提升。
