P2919 [USACO08NOV] Guarding the Farm S
[USACO08NOV] Guarding the Farm S P2919
农夫 John 的农场里有很多小山丘，他想要在那里布置一些保镖去保卫他的那些相当值钱的奶牛们。
他想知道如果在一座小山丘上布置一名保镖的话，他最少总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有 行和 列。矩阵中的每个元素都有一个值 来表示该地区的海拔高度。
小山丘的定义是：若地图中一个元素所邻接的所有元素都小于等于这个元素的高度（或它邻接的是地图的边界），则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是：若一个位置的横纵坐标与另一个位置的横纵坐标相差不超过 ，则称这两个元素邻接，比如某个非边界点的位置有 个相邻点：上, 下, 左, 右, 左上, 右上, 左下, 右下。
请你帮助他统计出地图上最少且尽量高的小山丘数量。
输入数据格式
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes row i of the matrix with M
space-separated integers: H_ij
输出数据格式
* Line 1: A single integer that specifies the number of hilltops
输入输出样例
| 输入 #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 | 3 |
说明与提示
There are three peaks: The one with height 4 on the left top, one of the points with height 2 at the bottom part, and one of the points with height 1 on the right top corner.