문제
밤하늘을 바라보면 반짝이는 별들이 여러 모양의 성단으로 나타나고 있는 걸 볼 수 있다.
성단이란 가로, 세로, 대각선으로 서로 이어져 있지 않은 별들의 집합이다.
성단은 다른 더 큰 성단의 일부가 될 수 없다. 한편, 닮은 성단이 존재할 수 있다.
90도 회전, 상하좌우 바꾸기를 통해서 서로 합동이 되게 할 수 있는 성단은 서로 닮았다고 한다.
일반적으로 존재할 수 있는 닮은 성단의 개수는 아래 그림과 같이 8개다.
밤하늘은 빈 곳은 0, 별이 있는 위치는 1의 정보를 갖는 이차원 행렬로 표현된다.
밤하늘 모습을 살펴보고, 개개의 성단을 소문자 알파벳으로 구분하여 표시하라.
단 닮은 성단끼리는 같은 글자로, 닮지 않은 성단끼리는 다른 글자로 표시하여야 한다.
성단을 나타내는 1을 알파벳으로 바꾸어 출력하면 된다.
입력
입력파일의 처음 두 줄에는 밤하늘의 지도의 가로(W), 세로(H)의 크기가 입력되며, 다음 줄부터 H줄에 W개의 0과 1로 이루어진 문자열이 입력된다. 아래 입력의 예와 같은 경우라면 밤하늘의 지도의 크기가 가로 23, 세로 15가 되며, 지도를 그림으로 표현하면 다음과 같다. 입력될 수 있는 성단의 개수는 500개 이하이며, 성단이 포함하는 별의 개수는 최대 160개 이하이며 지도의 크기는 최대 100 x 100 이다.
출력
문자 1을 문제 조건에 알맞은 알파벳으로 치환해서 출력한다. 사용하는 알파벳의 범위는 ‘a'~'z'로 가정한다. 이외의 알파벳을 사용하는 경우는 없다. 알파벳은 가장 위쪽에 위치하고, 가장 왼쪽에 위치할 경우의 패턴에 우선적으로 낮은 알파벳을 사용한다.
예제
23
15
100015000001500
01111100011111000101101
0150010001000111111
50000110100101111
0000011101000150000
0000100101111150000
15015050000
010100000111110010000
0000150100010011111
50011101011010010
0000010011010001500
0001000111011111500
00100
a000a500000b500
0aaaaa000ccccc000d0dd0d
0a500c000c000dddddd
50000c0b0c000d0dddd
00000eee0c000c50000
0000e00e0ccccc50000
b50e5050000
00b0f50ccccc00a0000
0000f50c000c00aaaaa
500ddd0c0b0c0a000a0
00000b00dd0c000c500
000g000ddd0ccccc500
00g0000ddd5
로그인해야 코드를 작성할 수 있어요.