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 如图所示，绿色单元格代表山谷：

:::align{center}

:::

数据范围

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

解析

枚举加判断，详见代码：

#include <bits/stdc++.h>
using namespace std;
//八个位置的偏移值
int dx[8]={1,1,1,0,0,-1,-1,-1};
int dy[8]={1,0,-1,1,-1,1,0,-1};
int n,m;
int a[105][105];
int cnt=0;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){//循环输入
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){//枚举每一个单元格
        for(int j=1;j<=m;j++){
            cnt++;//假定为山谷
            for(int k=0;k<8;k++){//枚举相邻的八个位置
                int x=i+dx[k];//计算行
                int y=j+dy[k];//计算列
                if (a[x][y]!=0&&a[x][y]<a[i][j]){//如果没出界（出界为0）并且比当前位置矮
                    cnt--;//不是山谷，减掉假定
                    break;//判断完毕，其他相邻位置不用再判断了，退出循环
                }
            }
        }
    }
    cout<<cnt;
	return 0;
}