4404 - Guarding the Farm

通过次数

0

提交次数

0

时间限制 : 1 秒
内存限制 : 128 MB

农场有许多小山丘,约翰农夫希望在这些小山丘上放置守卫,以确保他珍贵的奶牛的安全。

他想知道如果他希望在每个小山丘的顶部放置一个守卫,他需要多少守卫。他有一张地图,这张地图是一个整数矩阵;矩阵有 N 行(1 < N \leq 700)和 M 列(1 < M \leq 700)。矩阵中的每个元素表示一个高度 $H{ij}0 \leq H{ij} \leq 10,000$)。请帮助他确定地图上有多少个山顶。

一个山顶是由一个或多个相邻且具有相同值的矩阵元素组成,这些元素被地图的边缘或具有较低(较小)高度的元素完全包围。如果两个不同的元素的 X 坐标差的绝对值不大于 1,且 Y 坐标差的绝对值也不大于 1,则它们是相邻的。

输入

* 第 1 行:两个用空格分隔的整数:NM

* 第 2 行到第 N+1 行:第 i+1 行描述矩阵的第 i 行,包含 M 个用空格分隔的整数:H_{ij}

输出

* 第 1 行:一个整数,表示山顶的数量

样例

输入

8 7 
4 3 2 2 1 0 1 
3 3 3 2 1 0 1 
2 2 2 2 1 0 0 
2 1 1 1 1 0 0 
1 1 0 0 0 1 0 
0 0 0 1 1 1 0 
0 1 2 2 1 1 0 
0 1 1 1 2 1 0

输出

3

提示

有三个山峰:左上角高度为 4 的一个,底部高度为 2 的一个点,以及右上角高度为 1 的一个点。

来源

USACO