2518. Guarding the Farm

单点时限: 2.0 sec

内存限制: 256 MB

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 <= 100) rows and M (1 < M <= 70) 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 xclusively 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

样例

Input
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
Output
3
OUTPUT DETAILS:
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.

27 人解决,46 人已尝试。

28 份提交通过,共有 70 份提交。

5.0 EMB 奖励。

创建: 15 年,6 月前.

修改: 7 年,1 月前.

最后提交: 1 年,3 月前.

来源: USACO NOV 2008

题目标签
dfs