2013年7月11日 星期四

1103 - Ancient Messages

為了瞭解早期文明,考古學家同常研究古代語言中的文字。其中一種語言,在三千多年前的埃及被使用,將文字採用象形文字的方式記錄。如下圖, 表示六種象形文字以及對應的名字。

這一個問題中,你將要寫程式辨識這六個符號。


Input 

輸入有多組測資,每組包含一張圖片,其中會有數個描述的象形文字。 圖片格式是由水平掃瞄線包含黑色像素和白色像素,分別由 1, 0 表示。在輸入資料中,將會被表示成十六進制,例如:有八個像素 10011100 (1 是黑色, 0 是白色)將會被表示成 9c (十六進制),只有數字 '0'-'9' 和小寫 'a'-'f'。

第一行會有兩個整數 H, W  (0 < H <=200, 0 < W <= 50),表示接下來會有 H 行,每行上有 W 個十六進制的數字,圖片由上到下,由左而右。

輸入的圖片格式如下:
  • 圖片中只會有六種上述的象形文字
  • 每個圖片至少有一個象形文字
  • 每個黑色像素都是一個象形文字的一部分。
  • 每個象形文字的黑色像素部分,將由上下左右的方式連接。
  • 每個象形文字不會與其他象形文字碰觸。
  • 兩個在對角的黑色像素會有另一個共同的黑色像素。
  • 每個象形文字可能會失真,但是形狀的拓樸會是一樣的。


上面兩張圖分別是範例輸入的兩筆圖示。
 最後一組有兩個 0,不用處理。

Output 

對於每組測資,輸出測資編號,後接著一串字符,辨識出來的象形文字對應如下的字符:


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


輸出按照字母順序。

Sample Input 

100 25
0000000000000000000000000
0000000000000000000000000
...(50 lines omitted)...
00001fe0000000000007c0000
00003fe0000000000007c0000
...(44 lines omitted)...
0000000000000000000000000
0000000000000000000000000
150 38
00000000000000000000000000000000000000
00000000000000000000000000000000000000
...(75 lines omitted)...
0000000003fffffffffffffffff00000000000
0000000003fffffffffffffffff00000000000
...(69 lines omitted)...
00000000000000000000000000000000000000
00000000000000000000000000000000000000
0 0

Sample Output 

Case 1: AKW
Case 2: AAAAA