Problems
Ancient Messages
Ancient Messages
In order to understand early civilizations, archaeologists often study texts written in ancient languages. One such language, used in Egypt more than \textbf{3000} years ago, is based on characters called hieroglyphs. Figure \textbf{C.1} shows six hieroglyphs and their names. In this problem, you will write a program to recognize these six characters.
Figure \textbf{C.1}: Six hieroglyphs
\InputFile
The input consists of several test cases, each of which describes an image containing one or more hieroglyphs chosen from among those shown in Figure \textbf{C.1}. The image is given in the form of a series of horizontal scan lines consisting of black pixels (represented by \textbf{1}) and white pixels (represented by \textbf{0}). In the input data, each scan line is encoded in hexadecimal notation. For example, the sequence of eight pixels \textbf{10011100} (one black pixel, followed by two white pixels, and so on) would be represented in hexadecimal notation as \textbf{9c}. Only digits and lowercase letters \textbf{a} through \textbf{f} are used in the hexadecimal encoding. The first line of each test case contains two integers, \textbf{H} and \textbf{W}. \textbf{H} (\textbf{0} < \textbf{H} ≤ \textbf{200}) is the number of scan lines in the image. \textbf{W} (\textbf{0} < \textbf{W} ≤ \textbf{50}) is the number of hexadecimal characters in each line. The next \textbf{H} lines contain the hexadecimal characters of the image, working from top to bottom. Input images conform to the following rules:
\begin{itemize}
\item The image contains only hieroglyphs shown in Figure \textbf{C.1}.
\item Each image contains at least one valid hieroglyph.
\item Each black pixel in the image is part of a valid hieroglyph.
\item Each hieroglyph consists of a connected set of black pixels and each black pixel has at least one other black pixel on its top, bottom, left, or right side.
\item The hieroglyphs do not touch and no hieroglyph is inside another hieroglyph.
\item Two black pixels that touch diagonally will always have a common touching black pixel.
\item The hieroglyphs may be distorted but each has a shape that is topologically equivalent to one of the symbols in Figure \textbf{C.1} (Two figures are topologically equivalent if each can be transformed into the other by stretching without tearing).
\end{itemize}
The last test case is followed by a line containing two zeros.
\OutputFile
For each test case, display its case number followed by a string containing one character for each hieroglyph recognized in the image, using the following code:
\textbf{Ankh: A } \textbf{Wedjat: J } \textbf{Djed: D } \textbf{Scarab: S } \textbf{Was: W } \textbf{Akhet: K}
In each output string, print the codes in alphabetic order. Follow the format of the sample output.
The sample input contains descriptions of test cases shown in Figures \textbf{C.2} and \textbf{C.3}. Due to space constraints not all of the sample input can be shown on this page.
Input example #1
100 25 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 00000f8000000000000000000 00001fe000000000000000000 00007ff000000000000000000 00007ff800000000000000000 0000f8f800000000000000000 0001f07c00000000000000000 0001e03c00000000001800000 0001e01c00000000003c00000 0001c01c00000000007c00000 0003c01e0000000000f800000 0003c01e0000000001f000000 0001c01c0000000003f000000 0001c01c0000000007e000000 0001e01c000000000fc000000 0001e03c000000001fc000000 0000e03c000000001fc000000 0000f038000000003ff000000 0000f078000000003ff800000 00007870000000007ff800000 000038f0000000007cfc00000 00003ce0000000007c7c00000 00781fc0f0000000f87c00000 007ffffff0000000f07c00000 007ffffff0000000f07c00000 007ffffff0000001f07c00000 007ffffff0000000e03e00000 007fcf81f0000000603e00000 00000f8000000000003e00000 00000f8000000000003e00000 00000 ...
Output example #1
Case 1: AKW