题解：洛谷 B4501 [GESP202603 四级] 山之谷

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：B4501 [GESP202603 四级] 山之谷 - 洛谷

【题目描述】

现有一片山地，可以视为一个N NN行M MM列的网格图，第i ii行j jj列的海拔为h i , j h_{i,j}hi,j​。

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

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

【输入】

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

之后N NN行，每行包含M MM个整数h i , 1 , h i , 2 , ⋯ , h i , M h_{i,1}, h_{i,2}, \cdots, h_{i,M}hi,1​,hi,2​,⋯,hi,M​，表示海拔。

【输出】

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

【输入样例】

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

【输出样例】

3

【核心思想】

1. 问题分析：给定N × M N \times MN×M的海拔网格，需要统计"山谷"数量。山谷定义为海拔不高于所有8 88个方向相邻单元格（上、下、左、右及四个对角线方向）的单元格。这是一个网格遍历 + 方向枚举问题，核心在于对每个单元格检查其8 88个邻居的海拔关系。

2. 算法选择：

   • 方向向量枚举：预定义8 88个方向的偏移量( d x k , d y k ) (dx_k, dy_k)(dxk​,dyk​)，统一处理所有相邻位置
   • 逐格判定：遍历每个单元格，检查其所有合法邻居是否均≥ \geq≥当前单元格海拔

3. 关键步骤：

   • 读入数据：读取N , M N, MN,M和海拔矩阵h [ 1.. N ] [ 1.. M ] h[1..N][1..M]h[1..N][1..M]
   • 方向数组定义：d x = [ − 1 , − 1 , − 1 , 0 , 1 , 1 , 1 , 0 ] dx = [-1, -1, -1, 0, 1, 1, 1, 0]dx=[−1,−1,−1,0,1,1,1,0]，d y = [ − 1 , 0 , 1 , 1 , 1 , 0 , − 1 , − 1 ] dy = [-1, 0, 1, 1, 1, 0, -1, -1]dy=[−1,0,1,1,1,0,−1,−1]，对应8 88个相邻方向
   • 逐格判定山谷（遍历i ii从1 11到N NN，j jj从1 11到M MM）：
     • f l a g ← t r u e flag \leftarrow trueflag←true
     • 遍历8 88个方向，计算邻居坐标( n x , n y ) = ( i + d x k , j + d y k ) (nx, ny) = (i + dx_k, j + dy_k)(nx,ny)=(i+dxk​,j+dyk​)
     • 若邻居在边界内且h n x , n y < h i , j h_{nx,ny} < h_{i,j}hnx,ny​<hi,j​：f l a g ← f a l s e flag \leftarrow falseflag←false，b r e a k breakbreak
     • 若f l a g = t r u e flag = trueflag=true：c n t ← c n t + 1 cnt \leftarrow cnt + 1cnt←cnt+1
   • 输出结果：c n t cntcnt

4. 时间/空间复杂度：

   • 时间复杂度：O ( N ⋅ M ) O(N \cdot M)O(N⋅M)，每个单元格检查8 88个方向，共8 N M 8NM8NM次比较
   • 空间复杂度：O ( N ⋅ M ) O(N \cdot M)O(N⋅M)，存储海拔矩阵

5. 方向枚举与边界处理的核心思想：

   • 统一方向处理：通过预定义8 88个方向向量，将不同方向的邻居检查统一为坐标加法运算，避免重复编写边界判断逻辑
   • 提前终止优化：一旦发现某个邻居海拔严格小于当前单元格，立即判定不是山谷并跳出循环，减少不必要的比较
   • 边界安全判定：通过n x ∈ [ 1 , N ] nx \in [1,N]nx∈[1,N]且n y ∈ [ 1 , M ] ny \in [1,M]ny∈[1,M]的条件过滤越界邻居，确保不会访问数组非法位置
   • 不严格小于的判定：题目要求"不高于所有相邻单元格"，即h i , j ≤ h n e i g h b o r h_{i,j} \leq h_{neighbor}hi,j​≤hneighbor​对所有邻居成立，等价于不存在邻居h n e i g h b o r < h i , j h_{neighbor} < h_{i,j}hneighbor​<hi,j​
   • 适用于网格图上的局部极值统计、邻域关系判定类基础问题

【算法标签】

#普及- #模拟

【代码详解】

#include<bits/stdc++.h>// 包含所有标准库头文件usingnamespacestd;// 使用标准命名空间constintN=105;// 定义常量N，表示数组最大尺寸intn,m,cnt;// n:行数, m:列数, cnt:山谷计数器inta[N][N];// 定义二维数组a，存储地形高度// 定义8个方向向量，用于访问当前位置周围的8个邻居intdx[8]={-1,-1,-1,0,1,1,1,0};// x方向偏移：左、左上、上、右上、右、右下、下、左下intdy[8]={-1,0,1,1,1,0,-1,-1};// y方向偏移：上、上、上、右、右、右、下、下intmain()// 主函数入口{cin>>n>>m;// 输入矩阵的行数n和列数m// 读取矩阵数据for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){cin>>a[i][j];// 读取第i行第j列的高度}}// 遍历矩阵中的每一个位置for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){boolflag=1;// 标志位，表示当前位置是否是山谷，初始化为true// 检查当前位置的8个邻居for(intk=0;k<8;k++){// 计算邻居位置的坐标intnx=i+dx[k];// 邻居的x坐标intny=j+dy[k];// 邻居的y坐标// 检查邻居是否在矩阵范围内if(nx<1||nx>n||ny<1||ny>m){continue;// 如果邻居越界，跳过这个邻居}// 检查山谷条件：如果邻居高度小于当前位置高度，则不是山谷if(a[nx][ny]<a[i][j]){flag=0;// 标记当前位置不是山谷break;// 提前退出循环，不再检查其他邻居}}// 如果flag仍为1，说明所有邻居都不小于当前位置，当前位置是山谷if(flag){cnt++;// 山谷计数器加1}}}cout<<cnt<<endl;// 输出山谷的总数量return0;// 程序正常结束}

【运行结果】

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