农场有许多小山丘,约翰农夫希望在这些小山丘上放置守卫,以确保他珍贵的奶牛的安全。
他想知道如果他希望在每个小山丘的顶部放置一个守卫,他需要多少守卫。他有一张地图,这张地图是一个整数矩阵;矩阵有 N 行(1 < N \leq 700)和 M 列(1 < M \leq 700)。矩阵中的每个元素表示一个高度 $H{ij}(0 \leq H{ij} \leq 10,000$)。请帮助他确定地图上有多少个山顶。
一个山顶是由一个或多个相邻且具有相同值的矩阵元素组成,这些元素被地图的边缘或具有较低(较小)高度的元素完全包围。如果两个不同的元素的 X 坐标差的绝对值不大于 1,且 Y 坐标差的绝对值也不大于 1,则它们是相邻的。
* 第 1 行:两个用空格分隔的整数:N 和 M
* 第 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