纵横字谜的答案 Crossword Answers

有一个 $r$ 行 $c$ 列 $(1<r,c<10)$ 的网格，黑格为 `*` ，每个白格都填有一个字母。如果一个白格的左边相邻位置或者上边相邻位置没有白格（可能是黑格，也可能出了网格边界），则称这个白格是一个起始格。 你的任务是先找出网格中所有横向单词（`Across`）。这些单词必须从一个起始格（左边是黑格，或是第一列）开始，向右延伸到一个黑格的左边或者整个网格的最右列。然后找出所有竖向单词（`Down`），规则同上，这些单词必须从一个起始格（上边是黑格，或是第一行）开始，向下延伸到一个黑格的上边或者整个网格的最下行。 **【输入格式】** 有多个矩阵输入，对于第 $i$ 个矩阵，第一行输入 $r_i$ 和 $c_i$ 并以空格隔开。 $(1<r_i,c_i<10)$，表示此网格为 $r_i$ 行 $c_i$ 列，然后下面输入矩阵的内容，里面为大写字母或是 `*`，以 `0` 代表所有矩阵输入结束。 **【输出格式】** 每个谜题的输出包括谜题的标识符（如 `puzzle #1:`）和横向竖向单词列表。每个单词每行只输出一个并先输出以其相应定义的数量的递增顺序数字再输出单词。 数字的输出占据三个场宽并右对齐。 横向列表的标题是 `Across`，竖向单词列表的标题是 `Down`。 在列表为空的情况下（网格中的所有正方形均为黑色），`Across` 和 `Down` 标题仍应出现。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=168 [PDF](https://uva.onlinejudge.org/external/2/p232.pdf) 



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

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