《B4501 [GESP202603 四级] 山之谷》

题目背景

对应的选择、判断题：试题 - GESP 202603 C++ 四级 - 洛谷有题

题目描述

现有一片山地，可以视为一个 N 行 M 列的网格图，第 i 行 j 列的海拔为 hi,j​。

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

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

输入格式

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

之后 N 行，每行包含 M 个整数 hi,1​,hi,2​,⋯,hi,M​，表示海拔。

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

3

说明/提示

样例解释

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

数据范围

保证 1≤N,M≤100，1≤hi,j​≤105。

代码实现：

#include <iostream> #include <vector> using namespace std; int dx[] = {-1,-1,-1,0,0,1,1,1}; int dy[] = {-1,0,1,-1,1,-1,0,1}; int main() { int n,m; cin >> n >> m; vector<vector<int>> h(n,vector<int>(m)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >> h[i][j]; int ans = 0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { bool valley = true; for(int d=0;d<8;d++) { int x = i + dx[d]; int y = j + dy[d]; if(x>=0&&x<n&&y>=0&&y<m) { if(h[i][j] > h[x][y]) { valley = false; break; } } } if(valley) ans++; } } cout << ans; return 0; }