【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

3 5
7 6 6 7 9
6 5 6 7 6
6 5 7 8 9

输出 #1

3

说明/提示

样例解释

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

数据范围

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

---

题目分析

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

解题思路分为两步：

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

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

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

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

---

示例代码

#include <iostream>
#include <vector>

int main() {
    int N, M;
    std::cin >> N >> M;

    // 为了防止下标因为偏移计算越界，建议使用 N+2 和 M+2 大小的数组
    // 使用 std::vector 以支持可变的 N 和 M 动态大小分配，也可以直接声明静态大数组 int h[105][105]
    std::vector<std::vector<int>> h(N + 2, std::vector<int>(M + 2, 0));

    // 读入海拔高度（推荐起始下标为1，迎合我们一惯使用的坐标轴思维）
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            std::cin >> h[i][j];
        }
    }

    // 定义经典的方向数组（8个方向：左上, 上, 右上, 左, 右, 左下, 下, 右下）
    int dx[8] = {-1, -1, -1,  0, 0,  1, 1, 1};
    int dy[8] = {-1,  0,  1, -1, 1, -1, 0, 1};

    int ans = 0; // 记录山谷的总数量

    // 1. 全图扫描：依次检测地图中的每个坐标
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {

            bool isValley = true; // 默认它是个山谷，即“假设无罪”

            // 2. 八方向探测周围地形
            for (int k = 0; k < 8; k++) {
                int nx = i + dx[k]; // 算出邻居的横坐标
                int ny = j + dy[k]; // 算出邻居的纵坐标

                // 判断这个新算出的邻居坐标是否合法（不能越界跑出地图外）
                if (nx >= 1 && nx <= N && ny >= 1 && ny <= M) {

                    // 只要发现有一个合法的邻居，其海拔竟然严格”低于”中心点 (i,j)
                    if (h[nx][ny] < h[i][j]) {
                        isValley = false; // 说明中心点不是最低谷，推翻“假设”
                        break; // 后面的方向也不用看了，直接结束查岗
                    }
                }
            }

            // 8 个方向全部探查完毕并且中途没被推翻
            if (isValley) {
                ans++; // 山谷计数加一
            }
        }
    }

    // 输出最终找出的山谷数
    std::cout << ans << std::endl;

    return 0;
}

代码解析小贴士

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

---

所有代码已上传至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)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号