Informatica Online Judge

  두더지굴 [0475 / 01DB]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 406   Total Tried : 1768


The Champion of this Problem (C++) : gs16068 - ms / 548byte
My Best Submission (C++) : N/A

[]

Background

경곽이는 이어져있는 붙어 있는 두더지굴은 항상 한 마리의 두더지가 사는 집이라는 사실을 알게되었다.



경곽이는 뒷산에 몇 마리의 두더지가 사는지 궁금해졌다.

그래서 공중에서 특수촬영을 했다. 이 촬영으로 얻은 사진은 직사각형이고 가로 세로 1영역을 0또는 1로 표현한다. 0은 땅이고 1은 두더지굴을 나타낸다. 1이 연결되어 있으면 한 마리의 두더지가 사는 집으로 정의할 수 있다. 여기서 연결되었다는 것은 어떤 두더지굴이 상,하,좌,우로 연결된 경우를 말한다. 대각선상에 있는 경우는 연결된 것이 아니다.



<그림 2>는 <그림 1>을 두더지굴로 번호를 붙인 것이다. 특수촬영 사진 데이터를 입력받아 두더지굴수를 출력하고, 각 두더지굴의 크기(1의 개수)를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 가로, 세로의 크기를 나타내는 n이 입력된다. n은 30이하의 자연수
둘 째줄 부터 n줄에 걸쳐서 n개의 0과 1이 연속으로 입력된다.

Output

첫 째줄에 두더지 굴의 수를 출력한다.
둘 째줄부터 각 두더지 굴의 크기를 오름차순으로 한 줄에 하나씩 출력한다.

IO Example

입력
3
101
101
100

출력
2
2
3

출제 - 전민우(GSHS_28th)

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