第三部分编程题 第一题
《扫雷王国大冒险》
第一幕：欢迎来到扫雷王国
1、有一天，小杨来到了一个神秘王国。
（1）这里有很多土地。
例如：
□ □ □ □ □ □ □ □ □ □ □ □（2）可是……
有些土地下面埋着炸弹（雷）。
例如：
* □ * □ □ □ □ * □ * □ □（3）老师说：
小杨，现在你要做扫雷游戏。
要求：
如果当前位置不是雷。
请告诉别人：
它周围八个方向，一共有几个雷。
第二幕：什么叫相邻？
1、很多同学第一次学扫雷都会犯一个错误。
他们认为：
只有上下左右。
其实不是。
（1）扫雷里面：
八个方向都算相邻。
（2）例如：
□ □ □ □ ○ □ □ □ □中间这个○
需要检查：
↖ ↑ ↗ ← ○ → ↙ ↓ ↘（3）一共
8个方向。
这就是本题最先需要注意的。
第三幕：看看样例
1、题目输入：
3 4 4 1 1 1 3 2 4 3 2什么意思？
（1）第一行
3 4 4表示
3行 4列 4颗雷（2）后面四行：
1 1 1 3 2 4 3 2表示雷的位置。
（3）画出来：
* □ * □ □ □ □ * □ * □ □第四幕：我们先算一个格子
1、例如：
（1）第一行第二列。
就是这里：
* ○ * □ □ □ □ * □ * □ □看看周围。
左边 * 右边 * 左下 □ 下 □ 右下 □一共
2颗雷所以这里数字是
2（2）再例如：
第二行第二列。
* □ * □ □ ○ □ * □ * □ □看看八个方向。
左上 * 上 □ 右上 * 左 □ 右 □ 左下 * 下 □ 右下 □一共
3颗雷所以这里数字是
3所有的都计算后，输出样例的答案。
第五幕：怎样让计算机也会数？
1、假如你是计算机。
来到某个格子。
例如
(i,j)你怎么办？
2、一个一个写：
左 右 上 下 左上 右上 左下 右下太麻烦。
3、有没有一种办法？
一次解决八个方向？
答案：
可以使用方向数组。
第六幕：方向数组登场
1、我们画一个九宫格。
(-1,-1) (-1,0) (-1,1) (0,-1) 自己 (0,1) (1,-1) (1,0) (1,1)2、自己不用检查。
所以真正需要检查的是：
(-1,-1) (-1,0) (-1,1) (0,-1) (0,1) (1,-1) (1,0) (1,1)3、汉克老师告诉大家：
（1）可以手写数组，也可以直接两层循环。
for(di=-1;di<=1;di++)再
for(dj=-1;dj<=1;dj++)（2）于是：
(-1,-1) (-1,0) (-1,1) …… 一直到 (1,1)全部都会访问到
第七幕：不要忘记判断边界
1、例如：
（1）左上角。
○ □ □如果继续检查
左上就飞出地图了。
（2）所以必须判断：
是否越界？如果
小于0或者
大于等于n说明：
飞出地图。
直接跳过。
（3）代码中可以这样写：
if(i+di<0 || i+di>=n) continue;还有
if(j+dj<0 || j+dj>=m) continue;目的只有一个：
不要飞出地图。
第八幕：完整思路
同学们可以先画流程图。
开始 │ ▼ 读入 n m q │ ▼ 把所有雷存进二维数组 │ ▼ 枚举每一个格子 │ ▼ 是不是雷？ │ ├────是────►输出 * │ ▼ 不是雷 │ ▼ 统计八个方向 │ ▼ 输出数量 │ ▼ 结束第九幕：时间复杂度
1、假设：
地图
n行 m列2、每个格子：
检查
8个方向那么：
总次数：
n × m × 8因为8是常数。
3、所以复杂度：
O(nm)完全满足题目要求。
第十幕：参考代码
#include using namespace std; int mp[505][505]; int main() { int n, m, q; cin >> n >> m >> q; // 标记所有雷 for (int i = 0; i < q; i++) { int x, y; cin >> x >> y; mp[x - 1][y - 1] = -1; } // 枚举每一个格子 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // 如果是雷 if (mp[i][j] == -1) { cout << "* "; continue; } int cnt = 0; // 搜索自己与周围八个方向 for (int di = -1; di <= 1; di++) { for (int dj = -1; dj <= 1; dj++) { int nx = i + di; int ny = j + dj; // 越界 if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 是雷 if (mp[nx][ny] == -1) cnt++; } } // 搜索完输出雷的数量 cout << cnt << " "; } //不要忘记转行 cout << endl; } return 0; }最后，汉克老师送给同学们一句"扫雷口诀"
先标雷，再枚举；
不是雷，数八邻；
方向循环真方便；
越界立即跳过去；
统计完成就输出！
这道题真正想考什么？
这道题看起来是扫雷，其实真正考察的是二维数组的综合应用。通过这道题，同学们应该掌握四个非常重要的知识点：
二维数组存储地图——用数组表示整个棋盘。
二维数组遍历——两层
for循环依次访问每一个格子。八方向枚举——利用
di、dj两层循环一次性检查八个相邻位置，也可以直接使用定义的方向数组。边界判断——访问邻居之前必须先判断是否越界，这是以后学习BFS（广度优先搜索）、DFS（深度优先搜索）、图论等算法时最基础的技巧。