【GESP】C++四级真题 luogu-B4501, [GESP202603 四级] 山之谷

2026年3月，GESP四级真题，考察二维数组与八方向矩阵周围元素的探测验证，难度★★☆☆☆。洛谷难度级别：普及-。

B4501 [GESP202603 四级] 山之谷

题目要求

题目描述

现有一片山地，可以视为一个 $N$ 行 $M$ 列的网格图，第 $i$ 行 $j$ 列的海拔为 $h_{i,j}$ 。

如果一个单元格的海拔不高于其所有相邻单元格（相邻包括上、下、左、右、左上、右上、左下、右下，最多 $8$ 个方向）的海拔，则称该单元格为山谷。

请你数一数该片山地中有多少山谷。

输入格式

第一行包含 $2$ 个整数 $N, M$ ，表示山地的大小。

之后 $N$ 行，每行包含 $M$ 个整数 $h_{i,1}, h_{i,2}, \cdots, h_{i,M}$ ，表示海拔。

输出格式

输出 $1$ 行，包含 $1$ 个整数 $C$ ，表示山谷的数量。

输入输出样例 #1

输入 #1

Code 4 行

输出 #1

Code 1 行

13
2

说明/提示

样例解释

样例 1 如图所示，绿色单元格代表山谷：

数据范围

保证 $1 \leq N, M \leq 100$ ， $1 \leq h_{i,j} \leq 10^5$ 。

题目分析

本题是 GESP 四级典型的“二维数组（矩阵）遍历与探伤”问题。核心考察点在于：如何利用偏移量数组（常常被称为方向数组）优雅地遍历一个坐标周围的 8 个邻居，并在过程中处理矩阵边界越界的问题。

解题思路分为两步：

全图扫描： 使用标准的双重循环，遍历每一行 $i$ 和每一列 $j$ ，把地图上的每一个坐标 (i, j) 都当作“嫌疑山谷”拎出来检查。
八向探测： 对于当前检查的坐标 (i, j)，挨个检查它周围（最多 8 个）的邻居海拔。根据题意，“山谷”的定义是海拔不高于（即 $\le$ $\leq$ ）其所有相邻单元格。
- 只要我们发现在它合法的邻居周围，哪怕找到只有 1 个邻居的海拔比当前位置还要低，这就说明当前坐标根本不是最底部的山谷（违背了 $\le$ 的定义），应当立即否决（break 淘汰）。
- 如果挺过了周围所有合法邻居的检查，周围要么比它高，要么跟它一样高。它就是名副其实的“山谷”，计数器加一。

技巧点拨：方向数组 如果我们手动写 if 判断上下左右等 8 个方向以及它们的边界条件，代码会极度臃肿（需要写 8 个又长又臭的 if），非常容易由于复制粘贴而出错。标准的四级做法是定义两个分别代表 $x$ 坐标（行）和 $y$ 坐标（列）偏移量的常量数组：

C++ 2 行

1int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; // 行的上下变化
2int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; // 列的左右变化
3

在内围再套一层 0 到 7 的小循环，用它加上当前坐标 (i, j) 就生成了 8 个新邻居的坐标。配合边界条件 nx >= 1 && nx <= N && ny >= 1 && ny <= M 进行拦截保护。

示例代码

C++ 58 行

1#include <iostream>
2#include <vector>
3
4int main() {
5    int N, M;
6    std::cin >> N >> M;
7
8    // 为了防止下标因为偏移计算越界，建议使用 N+2 和 M+2 大小的数组
9    // 使用 std::vector 以支持可变的 N 和 M 动态大小分配，也可以直接声明静态大数组 int h[105][105]
10    std::vector<std::vector<int>> h(N + 2, std::vector<int>(M + 2, 0));
11
12    // 读入海拔高度（推荐起始下标为1，迎合我们一惯使用的坐标轴思维）
13    for (int i = 1; i <= N; i++) {
14        for (int j = 1; j <= M; j++) {
15            std::cin >> h[i][j];
16        }
17    }
18
19    // 定义经典的方向数组（8个方向：左上, 上, 右上, 左, 右, 左下, 下, 右下）
20    int dx[8] = {-1, -1, -1,  0, 0,  1, 1, 1};
21    int dy[8] = {-1,  0,  1, -1, 1, -1, 0, 1};
22
23    int ans = 0; // 记录山谷的总数量
24
25    // 1. 全图扫描：依次检测地图中的每个坐标
26    for (int i = 1; i <= N; i++) {
27        for (int j = 1; j <= M; j++) {
28
29            bool isValley = true; // 默认它是个山谷，即“假设无罪”
30
31            // 2. 八方向探测周围地形
32            for (int k = 0; k < 8; k++) {
33                int nx = i + dx[k]; // 算出邻居的横坐标
34                int ny = j + dy[k]; // 算出邻居的纵坐标
35
36                // 判断这个新算出的邻居坐标是否合法（不能越界跑出地图外）
37                if (nx >= 1 && nx <= N && ny >= 1 && ny <= M) {
38
39                    // 只要发现有一个合法的邻居，其海拔竟然严格”低于”中心点 (i,j)
40                    if (h[nx][ny] < h[i][j]) {
41                        isValley = false; // 说明中心点不是最低谷，推翻“假设”
42                        break; // 后面的方向也不用看了，直接结束查岗
43                    }
44                }
45            }
46
47            // 8 个方向全部探查完毕并且中途没被推翻
48            if (isValley) {
49                ans++; // 山谷计数加一
50            }
51        }
52    }
53
54    // 输出最终找出的山谷数
55    std::cout << ans << std::endl;
56
57    return 0;
58}
59

代码解析小贴士

假设推翻大法： 像判定“四周不能有任何一个元素比它小”这种典型的 “全局性” 判定条件，最好的手段就是先设一个布尔变量打上 true 的标记，随后在遍历邻居的循环里如果捉到了违规元素（这里是周围找到了海拔更低的点），就立刻打上 false 并 break 中断。循环结束后，如果变量依旧保持着 true，那它就是合格的。这种方法叫作标记推翻法，在检查素数或者做全排判断时也极为常用。
越界防护墙： 当你对二维数组当前的指针坐标做加减的偏移量运算后，新的坐标极有可能变成类似 (0, 3) 甚至 (-1, 5) 这类越界数组下标。务必在这行代码 if (nx >= 1 && nx <= N && ny >= 1 && ny <= M) 中牢牢锁死可操作空间！如果不加这行 if 拦截，程序就会发生 “数据越界”。越界会导致什么后果呢？有可能你取到了内存里其他地方的奇怪随机乱码（导致答案错误）；有可能运气更差，你越界访问到了操作系统规定“不许碰”的其他重要内存（比如其他程序正在用的内存空间），操作系统就会毫不客气地把你的程序直接强行关杀，并甩给你一个致命报错：段错误（Segmentation Fault）！所以，你一旦在各种 OJ 平台上看到“段错误”，第一反应就去查数组是不是越界了。