第三部分编程题 第一题《扫雷王国大冒险》第一幕欢迎来到扫雷王国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颗雷所以这里数字是22再例如第二行第二列。* □ * □ □ ○ □ * □ * □ □看看八个方向。左上 * 上 □ 右上 * 左 □ 右 □ 左下 * 下 □ 右下 □一共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;di1;di)再for(dj-1;dj1;dj)2于是(-1,-1) (-1,0) (-1,1) …… 一直到 (1,1)全部都会访问到第七幕不要忘记判断边界1、例如1左上角。○ □ □如果继续检查左上就飞出地图了。2所以必须判断是否越界如果小于0或者大于等于n说明飞出地图。直接跳过。3代码中可以这样写if(idi0 || idin) continue;还有if(jdj0 || jdjm) continue;目的只有一个不要飞出地图。第八幕完整思路同学们可以先画流程图。开始 │ ▼ 读入 n m q │ ▼ 把所有雷存进二维数组 │ ▼ 枚举每一个格子 │ ▼ 是不是雷 │ ├────是────►输出 * │ ▼ 不是雷 │ ▼ 统计八个方向 │ ▼ 输出数量 │ ▼ 结束第九幕时间复杂度1、假设地图n行 m列2、每个格子检查8个方向那么总次数n × m × 8因为8是常数。3、所以复杂度O(nm)完全满足题目要求。第十幕参考代码#include iostream 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深度优先搜索、图论等算法时最基础的技巧。