2521. 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 () rows and () columns. Each member of the matrix is an altitude ().

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 coordinates is no greater than and the magnitude of differences in their coordinates is also no greater than .

输入格式

  • Line 1: Two space-separated integers: and
  • Lines 2..: Line describes row of the matrix with space-separated integers:

输出格式

  • 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.

112 人解决,134 人已尝试。

222 份提交通过,共有 502 份提交。

2.8 EMB 奖励。

创建: 10 年,10 月前.

修改: 1 年,9 月前.

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

来源: USACO NOV 2008

题目标签
dfs