农场有许多山丘,Farmer John 想在上面安排守卫,保护他珍贵的奶牛。
若每个山顶都放一个守卫,他想知道需要多少人。他有一张整数矩阵地图,有 $N$ 行 $(1 \lt N \le 700)$ 和 $M$ 列 $(1 \lt M \le 700)$。每个元素是海拔 $H_{ij}$ $(0 \le H_{ij} \le 10,000)$。请帮他确定地图上的山顶数量。
山顶由一个或多个相邻且值相同的矩阵元素组成,其周围只能是地图边缘或海拔更低的元素。两个不同元素相邻,当且仅当它们的 $X$ 坐标之差的绝对值不超过 1,且 $Y$ 坐标之差的绝对值也不超过 1。
输入格式
- 第 1 行:两个空格分隔的整数 $N$ 和 $M$。
- 第 $2,\ldots,N+1$ 行:第 $i+1$ 行以 $M$ 个空格分隔的整数 $H_{ij}$ 描述矩阵的第 $i$ 行。
输出格式
- 第 1 行:一个整数,表示山顶数量。
样例
输入格式 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
输出格式 1
3
说明
共有三个山顶:左上角高度为 4 的点、底部某个高度为 2 的点,以及右上角某个高度为 1 的点。
题目作者:Fatih Gelgi,2008