GESP 题解库 / 4 级题解 / [GESP202603 四级] 山之谷 · 第 2 / 25 题
GESP202603 四级 · B4501 · 简单

山之谷

统计有多少个单元格,其海拔不高于周围 8 个相邻单元格的海拔。

📊
N, M ≤ 100
网格规模
🔢
海拔 ≤ 10⁵
数值范围
⚡
O(N × M)
时间复杂度
🎯
方向数组枚举
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定 N 行 M 列的网格,第 i 行 j 列的海拔为 h(i,j)。

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

请统计山谷的数量。

💡
人话翻译:对每个格子,把它周围 8 个邻居都看一遍,如果没有任何邻居比它更低(允许相等),它就是山谷。注意边界格子只有 5 个或 3 个邻居,不能把网格外的位置当作 0 或无限大。

🔍 关键词提取

8 邻域方向数组边界处理比较所有邻居

已知条件

项目说明
输入第一行 N、M;随后 N 行每行 M 个海拔
输出山谷的数量
数据范围1 ≤ N, M ≤ 100
海拔范围1 ≤ h ≤ 10⁵
判定条件该格 ≤ 所有相邻格(相等也算)

需要解决的问题

02
思维导图
整理解题思路的全貌
⛰️ 8 邻域逐个比较
📥 读入
N 行 M 列
二维数组 h[][]
N,M ≤ 100
注意下标从 0 或 1 开始
🧭 8 方向
dx = {-1,-1,-1,0,0,1,1,1}
dy = {-1,0,1,-1,1,-1,0,1}
配合循环枚举
边界要跳过
✅ 判定
对每个邻居比较
若存在更低 → 不是山谷
全部 ≥ 它 → 是山谷
相等也算通过
⚠️ 易错点
把"不高于"写成"低于"
越界没跳过
只考虑 4 邻域
数组开太小
03
样例手算推导
样例 3×5 网格逐格判定

🧮 样例逐格判定

网格如下,我们逐个格子检查它的 8 个邻居。

7 6 6 7 9
6 5 6 7 6
6 5 7 8 9
位置海拔相邻格中的最小值是否 ≤ 最小值
(1,1)75❌ 7 > 5
(1,2)65❌
(1,3)65❌
(1,4)76❌
(1,5)96❌
(2,1)65❌
(2,2)55✅ 5 ≤ 5
(2,3)65❌
(2,4)76❌
(2,5)67✅ 6 ≤ 7
(3,1)65❌
(3,2)55✅ 5 ≤ 5
(3,3)75❌
(3,4)86❌
(3,5)96❌
🔑
注意 (2,2) 这个格子:它海拔 5,周围有另一个 5(在 (3,2)),因为题目要求"不高于",所以相等也满足条件。如果写成严格小于,答案就会少算。
另外注意 (2,5):它海拔 6,邻居里最小值是 7,6 ≤ 7 成立,所以它是山谷。

🧮 边界格子怎么处理

四个角的格子只有 3 个邻居,边上的格子有 5 个。处理方法是越界就跳过,而不是把网格外当成 0。

位置类型邻居个数处理方式
内部格子8全部比较
边上(非角)5越界的 3 个方向跳过
四个角3越界的 5 个方向跳过
// 越界判断:只处理网格内的邻居
int nx = i + dx[d], ny = j + dy[d];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
⚠️
如果把网格外当成海拔 0,那么所有边上的格子都会"高于"这些虚拟的 0,于是永远不可能是山谷——正确答案会大幅偏少。这是本题最常见的错误。
04
解法对比
方向数组 vs 手写 8 个 if

⚔️ 解法对比

🟢 方向数组 + 循环(推荐) 推荐

用 dx/dy 两个数组配合循环枚举 8 个邻居

  • 时间 O(N × M × 8)
  • 代码 8 行搞定邻居遍历
  • 边界判断只需写一次
  • 扩展成 4 邻域很方便
💡
方向数组的写法:dx[8] = {-1,-1,-1,0,0,1,1,1}、dy[8] = {-1,0,1,-1,1,-1,0,1},两个数组同下标配成一组偏移。

🟠 手写 8 个判断

写 8 个 if 分别检查上、下、左、右、四个斜角

  • 代码冗长
  • 每个方向都要重复写边界判断
  • 容易漏掉某个方向
  • 不便于修改
⚠️
注意:手写 8 个方向时,每个都要写 i-1 >= 0 && j-1 >= 0 这样的边界判断,一共要写 8 次,出错概率明显更高。

📈 性能对比

方案代码量漏方向的概率
方向数组约 8 行低
手写 8 个 if约 30 行高
05
算法流程图
双层循环 + 8 邻域比较
开始读入 N、M 和网格 h[][];ans = 0i 从 0 到 N−1,j 从 0 到 M−1ok = trued 从 0 到 7,取邻居 (nx, ny)邻居越界吗?是 ✓跳过该方向否 ✗继续比较h[nx][ny] < h[i][j] 吗?是 ✗ok = false,退出内层否 ✓继续下一个方向ok 仍为 true 吗?是 ✓ans 加 1否 ✗不计数结束还有格子 → 继续判定
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

⛰️ 山谷检测器

第一行输入 N 和 M,随后 N 行每行 M 个数。程序会标出所有山谷。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int h[105][105];
// 8 个方向的偏移量:上、下、左、右、四个斜角
int dx[8] = {-1, -1, -1,  0, 0,  1, 1, 1};
int dy[8] = {-1,  0,  1, -1, 1, -1, 0, 1};

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            scanf("%d", &h[i][j]);

    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            bool ok = true;
            for (int d = 0; d < 8; d++) {
                int nx = i + dx[d], ny = j + dy[d];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;  // 越界跳过
                if (h[nx][ny] < h[i][j]) { ok = false; break; }        // 有更低的就不是山谷
            }
            if (ok) ans++;
        }
    }

    printf("%d\n", ans);
    return 0;
}
🔑
方向数组怎么记?把 8 个方向按"从上到下、从左到右"排列:第一行是 (-1,-1)、(-1,0)、(-1,1),中间是 (0,-1)、(0,1),最后是 (1,-1)、(1,0)、(1,1)。这样一眼就能看出覆盖了全部 8 个方向,不会漏也不会重。

📖 关键几行怎么看

代码作用为什么这样写
dx[8]、dy[8]方向偏移同下标配成一组,循环一次得一个邻居
if (nx < 0 || nx >= N ...) continue;越界判断越界就跳过,绝不能把界外当成 0
h[nx][ny] < h[i][j]判定条件只要有一个邻居更低,就不是山谷(注意是严格小于)
if (ok) ans++;计数所有邻居都不更低才算山谷
⚠️
三个坑:① 把"不高于"写成"低于",导致相等的格子被漏掉;② 越界没跳过(或把界外当 0),导致边界格子全部被误判;③ 只考虑了 4 邻域(上下左右),漏掉四个斜角方向。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 5
7 6 6 7 9 / 6 5 6 7 6 / 6 5 7 8 9
3题面样例
1 1
5
1单格没有邻居,条件自然成立,算山谷
2 2
1 1 / 1 1
4全部相等,每格都是山谷
3 3
9 9 9 / 9 1 9 / 9 9 9
1只有中心的 1 是山谷
1 3
5 3 5
1单行时左右两个邻居,3 是山谷
✅
自查清单:① 8 个方向都考虑了吗?② 越界跳过了吗?③ 相等的情况算作山谷吗?

🚨 易错点清单

⚠️
把界外当成海拔 0:边上的格子会"高于"这些 0,永远不可能是山谷,答案偏少。
⚠️
"不高于"写成"低于":题目允许相等,所以判定条件应是 邻居 < 自己 才淘汰,即自己 ≤ 所有邻居。
⚠️
只考虑 4 邻域:题目明确说包括 8 个方向,斜角方向也必须比较。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N × M × 8)
空间复杂度
O(N × M)
N, M 最大
100
最坏运算
约 8 × 10⁴

时间怎么算的?

空间都用在哪?

需要存整个网格,100 × 100 = 10⁴ 个整数。

✅ 8 万次比较,瞬间完成;这题的关键是方向数组和边界处理。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 4 邻域与 8 邻域的方向数组
int dx4[4] = {-1, 1, 0, 0};
int dy4[4] = { 0, 0,-1, 1};

int dx8[8] = {-1,-1,-1, 0, 0, 1, 1, 1};
int dy8[8] = {-1, 0, 1,-1, 1,-1, 0, 1};

// 通用邻居遍历模板
for (int d = 0; d < 8; d++) {
    int nx = i + dx8[d], ny = j + dy8[d];
    if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
    // 处理 (nx, ny)
}

// 用方向数组模拟"走迷宫"时也完全一样

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
方向数组用两个数组表示偏移网格搜索、迷宫、扫雷、BFS/DFS
越界跳过先判断再访问所有二维网格题目的必备写法
"不高于"语义相等也满足所有含"至少/至多/不超过"的判定
🌟
思考题:如果题目改成"海拔不高于所有相邻格且严格低于至少一个相邻格"(排除掉"平坦区域"),判定条件要加什么?(提示:再加一个标记"是否出现过严格更低或更高"——实际上这类定义在真实的地理题目(如山脊/山谷判定)里很常见。)