2463. Bad Grass

单点时限: 2.0 sec

内存限制: 256 MB

Bessie was munching on tender shoots of grass and, as cows do, contemplating the state of the universe. She noticed that she only enjoys the grass on the wide expanses of pasture whose elevation is at the base level of the farm. Grass from elevations just 1 meter

higher is tougher and not so appetizing. The bad grass gets worse as the elevation increases.

Continuing to chew, she realized that this unappetizing food grows the sides of hills that form a set of ‘islands’ of bad grass among the sea of tender, verdant, delicious, abundant grass.

Bessie donned her lab coat and vowed to determine just how many islands of bad grass her pasture had. She created a map in which she divided the pasture into R (1 < R <= 1,000) rows and C (1 < C <= 1,000) columns of 1 meter x 1 meter squares. She measured the

elevation above the base level for each square and rounded it to a non-negative integer. She noted hungrily that the tasty grass all had elevation 0.

She commenced counting the islands. If two squares are neighbors in any of the horizontal, vertical or diagonal directions then they are considered to be part of the same island.

How many islands of bad grass did she count for each of the supplied maps?

输入格式

  • Line 1: Two space-separated integers: R and C

  • Lines 2..R+1: Line i+1 describes row i of the map with C space

separated integers

输出格式

  • Line 1: A single integer that specifies the number of islands.

样例

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
2
OUTPUT DETAILS:
There are two islands. The big one on the left side that extends
all the way to the bottom through a diagonal and the small one on
the upper-right corner.

5 人解决,14 人已尝试。

8 份提交通过,共有 37 份提交。

8.3 EMB 奖励。

创建: 11 年,7 月前.

修改: 3 年前.

最后提交: 7 年,11 月前.

来源: USACO 2008 DEC

题目标签