Informatica Online Judge

  활동 영역 [1185 / 04A1]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 32   Total Tried : 65


The Champion of this Problem (C++) : gs15120 - 6ms / 1375byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

GS라는 물고기에 대한 연구를 하고 있다. GS는 수온이 일정하게 유지될 때, 안정적으로 활동할 수 있다고 한다.

연구를 위하여 직사각형 형태의 대형 수족관을 만들었다. 수족관의 크기는 세로, 가로가 각각 h, w이다. 각 단위영역의 온도를 조사한 결과 GS가 활동할 수 있는 곳은 1, 그렇지 않은 곳은 0으로 표시한 표를 만들었다.

이 표를 바탕으로 할 때, GS가 활동할 수 있는 총 영역의 수를 구하는 프로그램을 작성하시오.
(“활동할 수 있는 영역”이란 1로 표시된 임의의 영역으로부터 상, 하, 좌, 우로 인접한 1로 표시된 영역들의 집합(덩어리)을 의미한다.)

Input

첫 번째 줄에 수족관의 크기를 나타내는 정수 h와 w가 공백으로 구분되어 입력된다.
다음 줄부터 h줄에 걸쳐서 각 줄에 w개의 0 또는 1로 이루어진 문자열이 입력된다.

[Sub-task Info]
#1 : h, w <= 100 (70%)
#2 : h, w <= 1,000 (30%)

Output

최대 영역의 개수를 출력한다.

IO Example

입력1
3 4
1111
1000
1111

출력1
1

입력2
5 5
11111
10001
10101
10001
11111

출력2
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]