信息奥赛经典例题：地雷数计算与二维数组遍历技巧

1. 项目概述

"地雷数计算"是《信息奥赛一本通—编程启蒙》中的一道经典例题（编号3361），主要面向编程初学者和准备参加信息学奥赛的学生。这道题目通过模拟扫雷游戏中的数字计算过程，帮助学习者掌握二维数组遍历、边界条件判断等基础编程技巧。

作为编程启蒙阶段的典型题目，它完美融合了趣味性和教学性。题目要求根据给定的地雷分布图，计算每个格子周围的地雷数量，这与Windows经典扫雷游戏的数字生成逻辑完全一致。通过解决这个问题，学习者可以建立起对算法思维最直观的认识。

2. 问题解析与算法设计

2.1 题目要求详解

给定一个n×m的矩阵，其中''代表地雷，'.'代表空地。要求输出一个新矩阵，其中每个格子显示周围8个相邻格子中的地雷总数（地雷格子仍显示''）。

示例输入：

3 3 *.. ..* ...

对应输出：

*21 12* 011

2.2 核心算法思路

解决这个问题的关键在于设计一个高效的遍历算法：

1. 创建两个二维数组：一个存储原始地雷分布，另一个存储计算结果
2. 遍历每个非地雷格子，检查其8个相邻位置
3. 统计相邻地雷数量并存入结果数组
4. 地雷位置直接标记为'*'

2.3 方向数组技巧

为了简化相邻格子的检查，我们可以使用方向数组技术：

int dir[8][2] = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};

这样遍历时只需：

for(int k=0; k<8; k++){ int nx = i + dir[k][0]; int ny = j + dir[k][1]; // 检查(nx,ny)是否越界 }

3. 完整代码实现

3.1 C++实现版本

#include <iostream> using namespace std; const int MAXN = 105; char mine[MAXN][MAXN]; int result[MAXN][MAXN]; int main() { int n, m; cin >> n >> m; // 输入地雷图 for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin >> mine[i][j]; // 八方向数组 int dir[8][2] = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}}; // 计算每个格子的地雷数 for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ if(mine[i][j] == '*'){ result[i][j] = -1; // 标记为地雷 continue; } int count = 0; for(int k=0; k<8; k++){ int ni = i + dir[k][0]; int nj = j + dir[k][1]; if(ni>=1 && ni<=n && nj>=1 && nj<=m && mine[ni][nj]=='*') count++; } result[i][j] = count; } } // 输出结果 for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ if(result[i][j] == -1) cout << '*'; else cout << result[i][j]; } cout << endl; } return 0; }

3.2 代码优化技巧

1. 边界处理技巧：将数组声明为MAXN=105但只使用1-n行/列，空出0和n+1行列作为缓冲，可以简化边界条件判断

2. 输入优化：对于大规模数据，使用ios::sync_with_stdio(false)加速输入输出

3. 空间优化：可以只使用一个二维数组，原地修改（但会破坏原始数据）

4. 教学要点与常见错误

4.1 关键教学点

1. 二维数组的遍历方法：理解双重循环的行列遍历顺序
2. 边界条件处理：检查相邻格子时防止数组越界
3. 方向数组应用：学习这种简化多方向处理的编码技巧
4. 问题分解能力：将复杂问题拆分为遍历、检查、统计等子任务

4.2 常见错误分析

4.3 调试技巧

1. 打印中间结果：在统计每个格子的地雷数后，先输出中间结果检查
2. 小数据测试：先用3x3等小规模数据手动验证
3. 边界测试：专门测试矩阵四角和边缘的格子
4. 极端情况：全地雷或无地雷的特殊情况

5. 算法扩展与变种

5.1 性能优化方向

对于非常大的矩阵（如1000x1000），可以考虑：

1. 并行计算：将矩阵分块，多线程处理不同区域
2. 前缀和优化：使用二维前缀和数组快速查询任意矩形区域的地雷数
3. 稀疏矩阵处理：当地雷很少时，只记录地雷位置而非整个矩阵

5.2 题目变种示例

1. 六边形网格：相邻格子变为6个，修改方向数组即可
2. 三维扫雷：扩展为三维立方体，相邻格子增加到26个
3. 动态更新：支持地雷位置动态变化，要求实时更新数字
4. 图形化界面：结合GUI库实现可视化扫雷游戏

6. 教学实践建议

6.1 分阶段教学法

1. 理解阶段：先手动计算小样例，理解数字生成规则
2. 设计阶段：画出流程图，明确算法步骤
3. 实现阶段：先完成核心功能，再处理边界情况
4. 优化阶段：改进代码结构和性能

6.2 关联知识点

这道题目可以串联起多个编程基础知识点：

1. 二维数组的定义和使用
2. 多重循环结构
3. 条件判断语句
4. 函数封装（可将地雷计数部分提取为函数）
5. 输入输出处理

6.3 学习路线建议

完成此题后，可以继续挑战：

1. 实现完整的扫雷游戏（包括图形界面）
2. 学习更复杂的搜索算法（如DFS自动扫雷）
3. 研究扫雷问题的NP完全性证明
4. 尝试参加在线编程竞赛中的类似题目

提示：在教学实践中，可以让学生先玩几局扫雷游戏，直观理解数字含义，再过渡到编程实现，能显著提高学习兴趣和理解深度。