4030: 保卫农场

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:179 Solved:94

Description

农夫JOHN的农场里有很多小山丘,他想要在那里布置一些保镖去保卫他的那些相当值钱的奶牛们。 他想知道如果在一座小山丘上布置一名保镖的话,他总共需要招聘多少名保镖。他现在有一个用数字矩阵来表示地形的地图。这个矩阵有N行(1<N≤100)和M列(1<M≤70)。矩阵中的每个元素都有一个值H_ij(0≤H_ij≤10,000)来表示该地区的海拔高度。请你帮助他统计出地图上到底有多少个小山丘。 小山丘的定义是:若地图中一个元素所邻接的所有元素都比这个元素高度要小(或它邻接的是地图的边界),则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是:若一个元素与另一个横坐标纵坐标和它的横纵坐标相差不超过1,则称这两个元素邻接。(即某个非边界点跟它相邻的有8个点,上、下、左、右、左上、右上、左下、右下)

Input

第一行:两个由空格隔开的整数N和M。 第二行到第N+1行: 第I+1行描述了地图上的第I行,有M个由空格隔开的整数:H_ij。

Output

一个整数,表示小山丘的个数。

Sample Input Copy

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

Sample Output Copy

3

HINT

1、相邻相同属于同给一个地方 2、该地方周围都比他低,属于小山丘

加入题单

算法标签: