← 返回题目列表

AtCoder · joi2017yo_e

E. 岭

中文机器翻译题面 查看原题

配点: 100 点

問題

JOI火山口是一个美丽的地形,因其风景优美而受到许多登山爱好者的喜爱。从一个叫做山脊的地方看到的景色尤其壮观。

JOI火山口土地南北 H 公里,东西向 W 这是一个公里长的矩形。南北、东西向 1 将JOI火山口的土地划分为公里,并且 H \times W 区域称为区域。所有区域内的标高都是相同的。另外,不同地区的海拔高度也不同。

当某个地区下雨时,雨水会从北、南、东、西流入该地区。 4 它流向所有海拔低于该区域的区域。如果没有这样的区域,雨水就会聚集在该区域。从其他地区流出的雨水也是如此。 JOI火山口的外部被陡峭的索马悬崖包围,因此雨水不会从JOI火山口流出。

当只在某个区域下雨并且雨水最终聚集在多个区域时,该区域称为山脊。为喜爱壮丽景色的登山者编写一个程序来查找山脊区域的数量。


入力

输入是 有一条 1 + H 行组成。

1 在线 2 整数 H, W (1 \leqq H \leqq 1\,000,1 \leqq W \leqq 1\,000)以空格作为分隔符,JOI火山口位于南北。 H 公里,从东到西 W 代表公里距离。 每行

继续 H 每行有 W 整数以空格分隔,表示高度信息。H 行 i 线 j 番目 (1 \leqq i \leqq H,1 \leqq j \leqq W) 整数 M_{i, j} (1 \leqq M_{i, j} \leqq H \times W) 来自 JOI 火山口的北部。 i 行,从西边 j 表示列中区域的高程。(i, j) \neq (k, l) 然后,M_{i, j} \neq M_{k, l} 满意。

出力

山脊区域的数量为 在 1 行。


入力例 1

3 3
2 9 4
7 5 3
6 1 8

出力例 1

4

入力例 1 处,海拔高度为 5, 7, 8, 9 的 4 区域是山脊。例如,海拔高度 如果 9 地区下雨,雨水最终会到达海拔高度。 它累积在 1, 2, 3 的 3 区域。因此,海拔高度 区域 9 是一个山脊。还有海拔高度 它仅在 6 地区下雨,雨水最终会到达海拔高度。 它累积在 1 区域累积。因此,海拔高度 区域 6 不是山脊。


入力例 2

3 5
5 3 8 2 14
9 10 4 1 13
12 7 11 6 15

出力例 2

4

入力例 2 处,海拔高度为 8, 10, 11, 12 的 4 区域是山脊。 给出了