시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB112026118723.913%

문제

지민이는 보물을 찾아 떠나기 위해 섬과 바다가 그려져 있는 지도를 샀다. 지도는 N×M 크기의 직사각형 모양이고, 각각의 1×1크기의 칸에는 ‘x’ 또는 ‘.’중의 하나가 쓰여 있다.

바다는 ‘.’이 가로로 또는 세로로 최대로 연결되어 있는 그룹이다. 섬은 ‘x’가 가로, 세로, 또는 대각선으로 최대로 연결되어 있는 그룹이다.

만약 어떤 섬이 다른 섬을 포함하고 있지 않는다면, 그 섬은 높이가 0이다. 만약 어떤 섬A가 포함하고 있는 섬중에 가장 높이가 높은 섬의 높이가 K라면, 그 섬 A의 높이는 K+1이다.

섬 A가 섬 B를 포함한다는 말은, 일단 A와 B가 다르고, 섬 B의 어느 곳에서 출발해도 A의 밖으로 나갈 수 없을 때이다. 이때 대각선으로 이동은 불가능하다.

다음과 같은 지도를 보자.

xxx.x...xxxxx        000.0...11111
xxxx....x...x        0000....1...1
........x.x.x        ........1.4.1
..xxxxx.x...x        ..55555.1...1
..x...x.xxx.x        ..5...5.111.1
..x.x.x...x..        ..5.3.5...1..
..x...x...xxx        ..5...5...111
...xxxxxx....        ...555555....
x............        2............

섬은 총 6개가 있다. 높이가 0인 섬은 5개이다. (0~4) 그리고, 높이가 1인 섬은 1개 있다. (5) 3번 섬에서 출발해서 5번 섬의 밖으로 나갈 수 없기 때문에 섬5는 섬3을 포함하고 있는 것이다. 하지만, 섬4에서 출발해서 섬1을 나갈 수 있으므로, 섬1은 섬4를 포함하고 있는 것이 아니다.

지도가 주어졌을 때, 높이가 0인 섬의 개수부터 높이가 M인 섬의 개수까지를 차례대로 출력하는 프로그램을 작성하시오. M은 지도에 있는 섬 중에서 가장 높은 높이이다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 섬의 지도가 주어진다.

출력

첫째 줄에 높이가 0인 섬의 개수, 높이가 1인 섬의 개수, …, 높이가 M인 섬의 개수 까지 공백으로 구분해서 출력한다. 만약 섬이 하나도 없을 때는 -1을 출력한다.

예제 입력 1

10 5
xxxxx
x...x
x.x.x
x...x
xxxxx
xxxxx
x...x
x.x.x
x...x
xxxxx

예제 출력 1

2 1

예제 입력 2

1 1
x

예제 출력 2

1

예제 입력 3

5 5
xxxxx
x...x
x.x.x
x...x
xxxxx

예제 출력 3

1 1

예제 입력 4

2 2
..
..

예제 출력 4

-1

예제 입력 5

6 12
............
.......xxxx.
..xxx.x...x.
..x..x..x.x.
..x.x.x...x.
..xx...xxx..

예제 출력 5

1 1

출처