You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows.

He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns. Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000). Help him determine the number of hilltops on the map.

A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.

输入格式

* 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

题目大意

农夫 John 的农场里有很多小山丘，他想要在那里布置一些保镖去保卫他的那些相当值钱的奶牛们。

他想知道如果在一座小山丘上布置一名保镖的话，他最少总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有 $N$ 行和 $M$ 列。矩阵中的每个元素都有一个值 $H_{ij}$ 来表示该地区的海拔高度。

小山丘的定义是：若地图中一个元素所邻接的所有元素都小于等于这个元素的高度（或它邻接的是地图的边界），则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是：若一个位置的横纵坐标与另一个位置的横纵坐标相差不超过 $1$，则称这两个元素邻接，比如某个非边界点的位置有 $8$ 个相邻点：上、下、左、右、左上、右上、左下、右下。

请你帮助他统计出地图上最少且尽量高的小山丘数量。

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.