信息学奥赛‘流感传染’题解：二维数组与状态标记的艺术
在信息学奥赛的众多题目中，"流感传染"（1191题）是一个考察递推算法和状态处理的经典案例。这道题看似简单，却暗藏玄机——许多选手在初次尝试时都会掉入"当天感染当天传染"的逻辑陷阱。本文将深入剖析这一问题的核心难点，对比两种主流解法，并重点讲解如何用二维数组配合中间状态标记来优雅地解决问题。
1. 问题重述与核心难点
题目描述了一个n×n的网格状宿舍区，每个格子代表一个房间，可能住着健康的人（'.'）、空房间（'#'）或流感患者（'@'）。流感传播的规则是：每天，患者会传染其相邻（上下左右）的健康人群。我们需要计算第m天时的患者总数。
表面上看，这似乎是一个简单的网格遍历和状态更新问题。但仔细阅读题目描述会发现一个关键细节："以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变）"。这意味着：
- 新感染者在当天不具备传染性：只有前一天就已经是患者的人才能在当天传播病毒
- 传染存在一天延迟：当天被感染的人要到第二天才能传染他人
这一细微差别正是许多解题者容易忽略的地方。如果错误地认为当天被感染的人可以立即传染邻居，就会导致计算结果比实际值偏大。
2. 解法对比：三维数组 vs 二维数组
2.1 三维数组解法
最直观的解法是使用三维数组a[day][i][j]来记录每一天每个房间的状态。这种方法思路直接：
char a[105][105][105]; // 第i天第j行第k列的状态 for(int day = 2; day <= m; day++) { // 复制前一天的状态 for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { a[day][i][j] = a[day-1][i][j]; } } // 根据前一天的状态更新今天的感染情况 for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(a[day][i][j] == '.') { // 检查四个邻居在前一天是否有患者 if(a[day-1][i-1][j] == '@' || ... ) { a[day][i][j] = '@'; } } } } }优点：
- 逻辑清晰，直接对应题目描述
- 每天的状态独立存储，不易混淆
缺点：
- 空间复杂度高，为O(n²m)
- 对于大n和m的情况可能超出内存限制
- 需要复制前一天的全部状态，效率较低
2.2 二维数组解法（带中间状态）
更高效的解法是使用单个二维数组，通过引入中间状态来区分"新感染者"和"已有患者"：
char a[105][105]; // 当前各房间的状态 for(int day = 2; day <= m; day++) { // 标记新感染者 for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(a[i][j] == '.') { // 检查四个邻居是否有患者（不包括当天新感染的） if(a[i-1][j] == '@' || ... ) { a[i][j] = '*'; // 标记为当天新感染 } } } } // 将新感染者转为正式患者 for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(a[i][j] == '*') { a[i][j] = '@'; } } } }关键点：
- 使用特殊字符'*'标记当天新感染的人
- 传染性检查时只考虑'@'（前一天及更早的患者），忽略'*'
- 在一天结束时才将'*'转为'@'，确保第二天才有传染性
优势：
- 空间复杂度降至O(n²)
- 无需复制整个数组，效率更高
- 更符合实际编程竞赛中对空间和时间的严格要求
3. 二维数组解法的实现细节
让我们更详细地拆解二维数组解法的实现步骤：
3.1 初始化与输入处理
首先读取网格大小n，然后读取n×n的网格数据：
int n, m; char a[105][105]; cin >> n; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { cin >> a[i][j]; } } cin >> m;注意数组下标从1开始，这样可以利用默认初始化的0值作为边界保护，避免检查邻居时越界。
3.2 每日传播处理
对于每一天（从第2天到第m天），分两个阶段处理：
阶段一：标记新感染者
for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(a[i][j] == '.') { // 检查四个方向的邻居 bool infected = false; if(a[i-1][j] == '@') infected = true; if(a[i+1][j] == '@') infected = true; if(a[i][j-1] == '@') infected = true; if(a[i][j+1] == '@') infected = true; if(infected) { a[i][j] = '*'; // 标记为新感染 } } } }阶段二：将新感染者转为正式患者
for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(a[i][j] == '*') { a[i][j] = '@'; } } }3.3 结果统计
最后统计第m天的患者数量：
int cnt = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(a[i][j] == '@') { cnt++; } } } cout << cnt;4. 常见错误与调试技巧
在实现这一算法时，选手常会遇到以下问题：
4.1 边界检查问题
错误表现：数组越界导致程序崩溃或错误结果
解决方案：
- 将数组声明得比最大尺寸大一些（如105×105）
- 从1开始索引，利用0行和0列作为缓冲区
- 或者在访问邻居时显式检查边界：
if(i > 1 && a[i-1][j] == '@') ... if(i < n && a[i+1][j] == '@') ...4.2 状态更新顺序错误
错误表现：当天新感染的人立即具有传染性，导致结果偏大
解决方案：
- 严格分两个阶段处理：先标记所有新感染者，再统一转为患者
- 确保传染性检查时只考虑'@'，不包括'*'
4.3 特殊情况的处理
空房间处理：确保'#'房间不参与任何传染过程第1天处理：直接从第2天开始循环m=1的情况：直接统计初始患者数
5. 算法优化与扩展思考
5.1 性能优化
虽然O(n²m)的时间复杂度对于题目给定的限制（n,m≤100）已经足够，但我们可以考虑进一步优化：
- 使用位运算压缩状态表示
- 只跟踪患者位置的变化，而非全盘扫描
- 并行处理：利用SIMD指令加速邻居检查
5.2 问题变种
这一模型可以扩展为更复杂的传染病传播模拟：
- 不同传染概率
- 潜伏期和传染期的区分
- 免疫和康复机制
- 移动的人群（随时间变化的邻居关系）
5.3 与其他算法的联系
"流感传染"问题本质上是：
- 细胞自动机的特例（类似Conway的生命游戏）
- 图论中的广度优先搜索（BFS）问题
- 动态规划中的状态转移问题
理解这些联系有助于举一反三，解决更复杂的问题。
