【GESP】C++四级真题 luogu-B4557 [GESP202606 四级] 扫雷
GESP C++四级2026年6月真题。本题主要考查二维数组的使用和八方向邻域遍历。属于四级题中的基础题目。难度⭐⭐。本题在洛谷评定为普及-。
luogu-B4557 [GESP202606 四级] 扫雷
题目要求
题目描述
小杨同学正在游玩经典游戏「扫雷」，他想自己生成一个「扫雷」的地图。
小杨同学希望生成的地图大小为 $n$ 行 $m$ 列，一共 $n \times m$ 个区块。区块行号为 $1, 2, \cdots, n$，列号为 $1, 2, \cdots, m$。其中一些区块为雷区，其它区块不为雷区。
小杨同学指定了 $q$ 个区块为雷区，而其它区块均不为雷区。小杨同学希望你帮忙计算非雷区的区块，每个区块与多少个雷区相邻？
我们定义区块相邻，当且仅当两个区块至少有一个公共顶点（也就是说对于不在地图边缘的区块，周围 $8$ 个区块均与其相邻）。
输入格式
输入包含 $q + 1$ 行。
第一行，三个正整数 $n$, $m$ 和 $q$，分别表示地图行数和列数，以及雷区数量。
接下来的 $q$ 行，每行有 $2$ 个整数，分别表示第 $i$ 个雷区的行号和列号。
保证输入的雷区不重复。
输出格式
输出 $n$ 行，每行 $m$ 个字符（使用空格分割），对于第 $i$ 行第 $j$ 列，输出地图对应区块的信息：
- 如果为雷区，输出
*；- 如果不是雷区，输出其相邻雷区数量（输出 $0$ 到 $8$ 中的一个数字）。
输入输出样例 #1
输入 #1
1
2
3
4
5
3 4 4
1 1
1 3
2 4
3 2
输出 #1
1
2
3
* 2 * 2
2 3 3 *
1 * 2 1
说明/提示
根据输入，在 $3 \times 4$ 的地图上有 $4$ 个雷区，分别是 $(1,1)$，$(1,3)$，$(2,4)$ 和 $(3,2)$，如输出样例中 * 所示，其它非雷区区块的相邻雷区数量可以直观看出。
数据范围
$3 \le n, m \le 500$, $1 \le q \le n \cdot m$。
输入的雷区必定在地图内且不重复，注意行号和列号均从 $1$ 开始。
题目分析
本题是经典的扫雷地图生成问题，主要考察二维数组的使用和八方向邻域遍历。难度不高，属于模拟类题目。
1. 数据结构设计
- 使用二维布尔数组
mine[505][505]记录每个位置是否为雷区 - 使用方向数组
dx[8]和dy[8]表示八个方向的偏移量，便于遍历邻域 - 数组大小设置为 505 是为了满足题目要求的最大范围（$n, m \leq 500$），并留有余量
2. 核心算法思路
- 首先读入地图大小 $n$、$m$ 和雷区数量 $q$
- 将所有雷区位置标记在二维数组中
- 遍历整个地图的每个位置，如果是雷区，输出
*；如果不是雷区，遍历周围 $8$ 个方向，统计相邻的雷区数量并输出 - 注意边界判断：邻域坐标必须在 $[1, n] \times [1, m]$ 范围内
3. 算法复杂度分析
- 时间复杂度：标记雷区 $O(q)$，遍历地图并统计 $O(n \times m)$，总体 $O(n \times m)$
- 空间复杂度：存储地图信息 $O(n \times m)$，总体 $O(n \times m)$
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
// 二维数组记录每个位置是否为雷区
bool mine[505][505];
// 八个方向的偏移量：上、下、左、右、左上、右上、左下、右下
int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};
int main() {
// 读入地图行数、列数和雷区数量
int n, m, q;
std::cin >> n >> m >> q;
// 读入每个雷区的位置并标记
for (int i = 0; i < q; i++) {
int r, c;
std::cin >> r >> c;
mine[r][c] = true;
}
// 遍历整个地图
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 输出元素之间的空格分隔
if (j > 1) {
std::cout << " ";
}
if (mine[i][j]) {
// 当前位置是雷区，输出 '*'
std::cout << "*";
} else {
// 当前位置不是雷区，统计周围 8 个方向的雷区数量
int count = 0;
for (int d = 0; d < 8; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
// 判断邻域坐标是否在地图范围内
if (ni >= 1 && ni <= n && nj >= 1 && nj <= m && mine[ni][nj]) {
count++;
}
}
std::cout << count;
}
}
std::cout << std::endl;
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
