4228 - 고대의 문자

Time Limit: 1s Memory Limit: 128MB

Submissions: 9 Solved: 6

Description

고대시대에 "안아집트"라는 도시가 있었다. 성북천을 중심으로 부흥한 이 문명은 그들만의 문자를 가지고 있었다. 최근에 안아집트 시절부터 세워져있던 건축물 "J공학관"의 벽면에서 무수히 많은 벽화들이 발굴되서 화제가 되고있다.

고대 안아집트인들의 문자는 자연의 모습을 본따 만든 문자이며, 그 문자의 생김새는 아래 그림과 같다.

$\epsfbox{p5130a.eps}$

J공학관에서 얻어낸 벽화들은 매우 크고 많았기 때문에 사람의 눈으로 일일히 글자를 번역할 수가 없었다. 따라서 컴퓨터를 이용해 자동으로 글자들을 찾아내고자한다. 벽화그림이 흑백이미지로 주어졌을 때, 이 벽화에 써져있는 글자들이 무엇인지 알아내는 프로그램을 작성해보자.

Input

입력은 여러 테스트케이스로 이루어져있다.

각 테스트케이스는 하나의 벽화그림을 나타내며, 0은 흰색, 1은 검은색을 의미한다. 입력의 크기가 커질 수 있으므로 데이터는 16진수로 인코딩해서 주어진다. 예를 들어 01001101은 4d 로 나타낸다

첫째줄에는 벽화의 높이 H와, 벽화를 인코딩한 데이터의 문자 개수 W가 주어진다. (0 < H ≤ 200, 0 < W ≤ 50)

그 다음 H개의 줄에 걸쳐 벽화그림의 데이터가 주어진다.

벽화그림 데이터는 다음과 같은 조건을 만족한다.

위의 이미지에 있는 6개의 문자만 등장한다.
적어도 하나 이상의 문자를 포함하고있다.
검은색 픽셀은 모두 문자를 나타내는 픽셀이다. (노이즈 등이 존재하지 않음)
하나의 문자는 하나의 연결된 검은 픽셀들의 집합으로 볼 수 있으며, 검은색 픽셀의 상,하,좌,우 4개의 픽셀 중 하나는 적어도 검은색 픽셀이다.
문자는 서로 접하지 않으며, 한 문자 안에 다른 문자가 포함되는 경우도 없다.
대각선상에 위치한 두 검은 픽셀 사이에는 항상 공통적으로 이웃한 검은 픽셀이 존재한다.
입력으로 주어지는 문자는 삐뚤어져있을 수 있고, 늘어나있을 수도 있다. 하지만 위에 제시된 그림과는 위상학적으로 같은 모양새를 가지고있다. (문자를 찟지 않고, 적절한 변형을 통해서 원래 모양으로 만들 수 있다.)

H W가 각각 0 0 으로 주어지면 입력을 마친다.

Output

각 테스트케이스마다 한줄에 하나씩 아래의 포멧을 따라 정답을 출력한다.

Case k: X

k는 테스트케이스의 번호이며(1부터 시작) X는 정답을 나타내는 문자열이다.

X는 벽화에 있는 글자들의 약자들을 모아놓은 문자열인데. 문자들의 약자는 다음과 같다.

Ankh: A
Wedjat: J
Djed: D
Scarab: S
Was: W
Akhet: K

문자가 여러번 등장하면 등장한 횟수만큼 출력하며, X에는 약자가 사전순으로 빠른 문자부터 출력한다.

Sample Input

데이터가 매우 크므로 구글 드리아브 문서로 대체함
https://drive.google.com/file/d/0B2-TGBptV6YjeUNwWmhUcWM2Tms/view?usp=sharing

Sample Output

Case 1: AKW
Case 2: AAAAA

Hint

Source

World Finals, 2011 - Orlando