从‘流感传染’到‘图搜索’：用C++队列优化算法，带你吃透NOI/OpenJudge经典题-开发者社区

从‘流感传染’到‘图搜索’：用C++队列优化算法，带你吃透NOI/OpenJudge经典题

在信息学竞赛的征途中，算法优化往往能决定胜负。今天我们就以OpenJudge经典题目"流感传染"为例，深入探讨如何通过队列优化将朴素解法从O(mn²)提升到O(n²)级别。这道题看似简单，却蕴含着广度优先搜索(BFS)和图论优化的核心思想，是理解算法效率差异的绝佳案例。

1. 问题建模与朴素解法

流感传染题目描述了一个n×n的网格，其中'@'代表感染者，'.'代表健康者。每天感染者会传染相邻的健康者，我们需要计算m天后总感染人数。乍看之下，这似乎只需要简单的二维数组遍历就能解决。

1.1 二维数组遍历实现

最直观的解法是每天遍历整个网格，检查每个健康者周围是否有感染者：

for(int k = 2; k <= m; ++k) { // 第k天 memset(t, 0, sizeof(t)); for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { t[i][j] = mp[i][j]; if(mp[i][j] == '.') { // 检查四个方向 for(int l = 0; l < 4; ++l) { int x = i + dir[l][0], y = j + dir[l][1]; if(x >= 1 && x <= n && y >= 1 && y <= n && mp[x][y] == '@') { t[i][j] = '@'; } } } } } memcpy(mp, t, sizeof(t)); }

这种解法虽然正确，但存在明显的效率问题：

重复检查：已经感染的人会被反复检查
无效传播：感染者在传染后第二天不会再产生新的传播
空间浪费：需要额外的临时数组保存中间状态

1.2 复杂度分析

假设网格大小为n×n，天数为m：

时间复杂度：O(mn²)
空间复杂度：O(n²)

当n=100，m=100时，运算次数将达到惊人的1,000,000次。这在竞赛中很可能导致超时。

2. 队列优化与BFS思想

仔细观察传染过程，我们会发现只有新感染者才会在第二天传播病毒。这正是BFS算法的核心特征——逐层扩展。我们可以用队列来优化这个过程。

2.1 BFS解法核心思路

初始化队列：将所有初始感染者入队
逐层处理：
- 出队一个感染者
- 检查其四个方向的健康者
- 将新感染者入队，并记录感染天数
终止条件：
- 队列为空（所有可能感染者都已处理）
- 达到指定天数m

struct Node { int x, y, d; }; // 坐标和感染天数 queue<Node> que; // 初始感染者入队 for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { if(mp[i][j] == '@') { que.push(Node{i, j, 1}); } } } while(!que.empty()) { Node u = que.front(); que.pop(); ct++; if(u.d == m) continue; // 第m天感染者不再传播 for(int i = 0; i < 4; ++i) { int x = u.x + dir[i][0], y = u.y + dir[i][1]; if(x >= 1 && x <= n && y >= 1 && y <= n && !vis[x][y] && mp[x][y] == '.') { mp[x][y] = '@'; que.push(Node{x, y, u.d + 1}); } } }

2.2 复杂度对比

指标	朴素解法	BFS优化
时间复杂度	O(mn²)	O(n²)
空间复杂度	O(n²)	O(n²)
实际运算量	1,000,000	10,000

BFS解法之所以高效，是因为它：

避免重复处理：每个感染者只处理一次
精准传播：只传播可能产生新感染的方向
即时终止：达到天数后立即停止传播

3. 从具体问题到通用算法

这道题目看似简单，实则蕴含着图论算法的精髓。我们可以将其抽象为一个图论问题：

顶点：每个网格单元
边：相邻网格之间的连接
传播过程：从源点开始的广度优先遍历

3.1 与经典算法的关联

这种优化思路与图论中的两个重要算法高度相关：

Bellman-Ford vs SPFA：
- 朴素解法类似Bellman-Ford，每次都松弛所有边
- BFS优化类似SPFA，只松弛可能产生更新的边
Dijkstra算法：
- 普通BFS相当于边权为1的最短路径问题
- 这里的"天数"实际上就是最短路径长度

3.2 通用BFS框架

通过这道题，我们可以总结出一个通用的BFS解题框架：

定义状态结构体：包含必要的信息（如坐标、步数等）
初始化队列：将初始状态入队
处理队列：
- 出队一个状态
- 检查终止条件
- 生成新状态并入队
访问控制：避免重复处理（如vis数组）

struct State { /* 所需字段 */ }; queue<State> q; bool vis[N][N]; // 访问标记 // 初始化 q.push(initialState); vis[initX][initY] = true; while(!q.empty()) { State curr = q.front(); q.pop(); // 处理当前状态 for(/* 每个相邻状态 */) { if(/* 状态合法且未访问 */) { vis[newX][newY] = true; q.push(State{newX, newY, curr.step + 1}); } } }

4. 实战技巧与常见陷阱

在实际编码实现时，有几个关键点需要特别注意：

4.1 输入处理细节

边界处理：确保数组访问不越界
输入缓冲：注意换行符的处理，特别是在混合使用cin和scanf时

cin >> n; // 清除可能的换行符 cin.ignore(); for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { cin >> mp[i][j]; } }

4.2 常见错误模式

忘记标记已访问：导致重复入队和无限循环
天数计算错误：混淆当前天数和下一天
初始状态遗漏：未将所有初始感染者入队
边界条件处理不当：数组下标从0还是1开始

4.3 调试技巧

打印中间状态：在关键步骤输出队列内容和网格状态
小规模测试：先用3×3或4×4网格验证逻辑
边界测试：测试m=1和m很大的情况

// 调试打印 void printQueue(queue<Node> q) { while(!q.empty()) { Node u = q.front(); q.pop(); cout << "(" << u.x << "," << u.y << ") day:" << u.d << " "; } cout << endl; }