#joi2017yoe. [joi2017yo_e]尾根 (Ridge)

[joi2017yo_e]尾根 (Ridge)

问题

JOI卡尔德拉是一个风景优美、深受登山爱好者喜爱的美丽地区。尤其是从被称为“尾根”的地方眺望,景色壮丽。

JOI卡尔德拉的土地是一个南北长为HH公里,东西长为WW公里的长方形。将JOI卡尔德拉的土地每隔一公里划分为一块,这H×WH \times W个区域被称为区域。在每个区域内,高度是相等的。而不同区域的高度是不同的。

当某个区域下雨时,雨水会流向其东、西、南、北相邻的最多4个区域中的所有高度低于该区域的区域。如果不存在这样的区域,则雨水会积聚在该区域中。对于从其他区域流来的雨水也是同样的处理。由于JOI卡尔德拉外部被陡峭的外侧山围绕着,雨水不会流出JOI卡尔德拉。

给定一个区域,当只有该区域下雨时,最终多个区域会积聚雨水时,我们称该区域为尾根。现在请你编写一个程序,以求出尾根的个数,以满足钟爱壮丽景色的登山者们的需求。


输入

输入由 1+H1 + H 行构成。

第一行包含两个整数 H,WH, W (1H1,0001 \leqq H \leqq 1,0001W1,0001 \leqq W \leqq 1,000),表示JOI卡尔德拉的南北长度为 HH 公里,东西长度为 WW 公里。

接下来的 HH 行,每行包含 WW 个整数,以空格分隔,表示高程信息。在这些行中,第 ii 行第 jj 个整数 Mi,jM_{i,j} (1Mi,jH×W1 \leqq M_{i,j} \leqq H \times W) 表示JOI卡尔德拉中从北向南第 ii 行,从西向东第 jj 列的区域的高程。当 (i,j)(k,l)(i, j) \neq (k, l) 时,必有 Mi,jMk,lM_{i,j} \neq M_{k,l}

输出

输出一个整数,表示尾根的个数。


输入例子 1

3 3
2 9 4
7 5 3
6 1 8

输出例子 1

4

在输入例子 1 中,高程为 5、7、8、9 的四个区域是尾根。例如,如果某个区域下雨,最终雨水会积聚在高程为 1、2、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 的四个区域都是尾根。