从‘流感传染’到‘图搜索’：用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解法核心思路

1. 初始化队列 ：将所有初始感染者入队
2. 逐层处理 ：
   • 出队一个感染者
   • 检查其四个方向的健康者
   • 将新感染者入队，并记录感染天数
3. 终止条件 ：
   • 队列为空（所有可能感染者都已处理）
   • 达到指定天数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解法之所以高效，是因为它：

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

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

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

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

3.1 与经典算法的关联

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

1. Bellman-Ford vs SPFA ：

   • 朴素解法类似Bellman-Ford，每次都松弛所有边
   • BFS优化类似SPFA，只松弛可能产生更新的边

2. Dijkstra算法 ：

   • 普通BFS相当于边权为1的最短路径问题
   • 这里的"天数"实际上就是最短路径长度

3.2 通用BFS框架

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

1. 定义状态结构体 ：包含必要的信息（如坐标、步数等）
2. 初始化队列 ：将初始状态入队
3. 处理队列 ：
   • 出队一个状态
   • 检查终止条件
   • 生成新状态并入队
4. 访问控制 ：避免重复处理（如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 常见错误模式

1. 忘记标记已访问 ：导致重复入队和无限循环
2. 天数计算错误 ：混淆当前天数和下一天
3. 初始状态遗漏 ：未将所有初始感染者入队
4. 边界条件处理不当 ：数组下标从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;
}

5. 扩展思考与举一反三

掌握了这个案例后，我们可以将其应用到更广泛的场景中：

5.1 变种问题

1. 多源点BFS ：多个初始感染者（如本题）
2. 带权BFS ：不同方向的传播速度不同
3. 障碍物处理 ：某些网格不可传播
4. 动态变化 ：感染者和健康者会移动

5.2 实际应用场景

1. 社交网络传播 ：信息或疾病的传播模型
2. 图像处理 ：区域填充算法
3. 游戏AI ：路径寻找和地图探索
4. 网络爬虫 ：网页抓取的调度策略

5.3 进一步优化方向

1. 双向BFS ：当目标状态明确时
2. 启发式搜索 ：结合估价函数
3. 并行处理 ：利用多线程加速
4. 内存优化 ：使用位运算压缩状态

在NOI/OpenJudge等竞赛中，这类题目层出不穷。比如"迷宫问题"、"八数码"、"马的遍历"等，都可以套用这个BFS框架。理解了这个案例的精髓，你就掌握了解决一大类问题的钥匙。