#G1161. [GESP202603 四级] 山之谷

[GESP202603 四级] 山之谷

[GESP202603 四级] 山之谷

时间限制:1.0 s,内存限制:512.0 MB

题目描述

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

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

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

输入格式

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

之后 NN 行,每行包含 MM 个整数 hi,1,hi,2,…,hi,Mh_{i,1}, h_{i,2}, \dots, h_{i,M},表示海拔。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

3

样例解释

样例 1 中共有 3 个山谷(第二行第二列、第三行第二列、第二行第五列,均不高于其所有相邻单元格的海拔)。

数据范围

  • 保证 1≤N,M≤1001 \le N, M \le 100,1≤hi,j≤1051 \le h_{i,j} \le 10^5。