G4023 [GESP202603 四级] 山之谷 题解

知识点：二维数组、邻域判断、边界处理。

解题思路

逐格检查与其相邻的八个方向及自身，若不存在更低邻格，该格就是山谷。

为什么正确

对所有存在的邻格验证“高度不低于中心”，与局部最低定义等价。

易错点

边界只检查实际存在的格子；相同高度允许，因此比较为邻格小于中心时才失败。

复杂度

时间O(nm)，空间O(nm)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>a(n,vector<int>(m));
    for(auto &row:a)for(int &x:row)cin>>x;
    int ans=0;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++) {
        bool ok=true;
        for(int x=max(0,i-1);x<=min(n-1,i+1);x++)for(int y=max(0,j-1);y<=min(m-1,j+1);y++)if(a[x][y]<a[i][j])ok=false;
        ans+=ok;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。