프로그램 명: usa_badgras
제한시간: 1 초

[요약] R * C 행렬이 주어질 때 인접한 0 이외의 숫자들의 블록 수를 구하는 문제. 좌/우/대각선으로 연결되면 같은 블록으로 간주.

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: A single integer that specifies the number of islands.

입출력 예

입력

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

출력

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. 
출처:usaco 2008 DEC bronze
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]