C. 고대의 메시지

고대 문명을 이해하기 위해 고고학자들은 옛 언어로 쓰인 문헌을 연구하곤 한다. 3000년도 더 전에 이집트에서 쓰인 그런 언어 중 하나는 히에로글리프라고 불리는 문자에 기반한다. 그림 C.1은 여섯 개의 히에로글리프와 그 이름을 보여 준다. 이 문제에서는 이 여섯 문자를 인식하는 프로그램을 작성한다. Ankh Wedjat Djed Scarab Was Akeht 그림 C.1: 여섯 개의 히에로글리프

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 그림 C.1에 있는 히에로글리프를 하나 이상 포함하는 이미지를 설명한다. 이미지는 검은 픽셀(1로 표현)과 흰 픽셀(0으로 표현)로 이루어진 가로 스캔 라인의 나열로 주어진다. 입력 데이터에서 각 스캔 라인은 16진수 표기로 인코딩된다. 예를 들어 여덟 픽셀의 나열 10011100(검은 픽셀 하나, 그 뒤 흰 픽셀 둘, 이런 식)은 16진수 표기로 9c로 표현된다. 16진수 인코딩에는 숫자와 소문자 a부터 f까지만 사용된다. 각 테스트 케이스의 첫 줄에는 두 정수 \(H\)와 W가 주어진다. H (\(0 < H \le 200\))는 이미지의 스캔 라인 수이다. \(W\) (\(0 < W \le 50\))는 각 줄의 16진수 문자 수이다. 다음 \(H\)개의 줄에는 이미지의 16진수 문자가 위에서 아래 순서로 주어진다. 입력 이미지는 다음 규칙을 따른다.

• 이미지는 그림 C.1에 있는 히에로글리프만 포함한다.

• 각 이미지는 유효한 히에로글리프를 적어도 하나 포함한다.

• 이미지의 모든 검은 픽셀은 유효한 히에로글리프의 일부이다.

• 각 히에로글리프는 연결된 검은 픽셀들의 집합이며, 모든 검은 픽셀은 상하좌우 중 적어도 한 방향에 다른 검은 픽셀이 있다.

• 히에로글리프들은 서로 닿지 않으며, 어떤 히에로글리프도 다른 히에로글리프 안에 있지 않다.

• 대각선으로 닿는 두 검은 픽셀은 항상 공통으로 닿는 검은 픽셀을 가진다.

• 히에로글리프는 찌그러져 있을 수 있지만, 각각은 그림 C.\(1^{1}\)의 기호 중 하나와 위상적으로 동등한 모양이다. 마지막 테스트 케이스 다음에는 0 두 개가 있는 줄이 주어진다. ^{1}두 도형을 찢지 않고 늘이는 것만으로 서로 변환할 수 있으면 두 도형은 위상적으로 동등하다.

각 테스트 케이스마다 케이스 번호와 함께, 이미지에서 인식된 각 히에로글리프마다 다음 코드에 따라 문자 하나씩을 포함하는 문자열을 출력한다. Ankh: A Wedjat: J Djed: D Scarab: S Was: W Akhet: K 각 출력 문자열에서 코드는 알파벳 순서로 출력한다. 샘플 출력의 형식을 따른다. 샘플 입력에는 그림 C.2와 C.3에 나온 테스트 케이스의 설명이 들어 있다. 지면 관계상 샘플 입력 전체를 이 페이지에 실을 수는 없다. 그림 C.2: AKW 그림 C.3: AAAAA

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2011