232 - Crossword Answers

猜字謎的遊戲包含一個由黑與白區塊所組成的棋盤方格，另外提供兩列單字。其中的一列為棋盤中由左到右白色方格中橫列的單字，另一列為由上到下白色方格中直行的單字。為了解出猜字謎遊戲，玩家從所提供的兩列單字從填入白色方格中。

為了找出棋盤方格中的所有單字，首先必須對所有「適合的(eligible)」白色方格依序做編號，其左方或上方為「黑色方格或沒有方格」的所有白色方格稱為「適合的」，並將所有適合的白色方格由上到下，由左至右依序做編號，如下圖所示：

猜字謎中的「橫列單字」為橫列中由左到右的每一組單字，「直行單字」為直行中由上到下的每一組單字。

請你寫一個程式從已經解決的字謎遊戲中找出所有「橫列單字」與「直行單字」並以編號大小排列輸出。

Input

每組測試資料的第一列有兩個整數 r 與 c (1 <= r, c <= 10)，r 表示猜字謎遊戲的列數，c 表示行數。接下來會有 r 列，每列 c 個字元，以英文字母表示被填滿的白色方格，以 * 表示黑色方格。以一列 r = 0 表示測試資料結束。

Output

請對每組測試資料輸出資料編號(puzzle #1, puzzle #2, ...)，接著輸出「橫列單字」與「直行單字」，橫列單字前請輸出一列"Across"，直行單字前請輸出"Down"，每個單字請以第一個字母的編號依序輸出，請參考測試資料。

請在每組測試資料之間以一列空行隔開。

Sample Input

2 2
AT
*O
6 7
AIM*DEN
*ME*ONE
UPON*TO
SO*ERIN
*SA*OR*
IES*DEA
0

Sample Output

puzzle #1:
Across
  1.AT
  3.O
Down
  1.A
  2.TO

puzzle #2:
Across
  1.AIM
  4.DEN
  7.ME
  8.ONE
  9.UPON
 11.TO
 12.SO
 13.ERIN
 15.SA
 17.OR
 18.IES
 19.DEA
Down
  1.A
  2.IMPOSE
  3.MEO
  4.DO
  5.ENTIRE
  6.NEON
  9.US
 10.NE
 14.ROD
 16.AS
 18.I
 20.A

原文出處