← 返回题目列表

AtCoder · icpc2012autumn_g

G. 古代纪念巨石

中文机器翻译题面 查看原题

问题陈述

有一天,爱丽丝在森林里发现了一块古老的巨石。

她调查了巨石,发现这是用古老语言写的句子。 句子由字形和围绕它们的矩形组成。 对于上面的示例,有以下字形。

请注意,句子中的某些字形会水平翻转。

她决定使用 ASCII 字母对其进行音译,为每个字形分配一个字母表,并且 [ 和 ] 到矩形。 如果一个句子包含翻转字形,她会从右向左音译。 例如,她可以分配 a 和 b 分别对应上述字形。 那么上面这句话就可以音译为 [[ab][ab]a].

检查完这个句子后,Alice 发现这个句子的结构如下:

  • 句子<seq>是由零个或多个<term>组成的序列。
  • 术语 <term> 是字形或 <box>。字形可以被翻转。
  • <box> 是围绕 <seq> 的矩形。盒子的高度比里面任何字形都大。

现在,写在巨石上的句子是一个非空的 <seq>。 序列中的每个术语都适合一个矩形边界框,尽管这些框没有明确指示字形。 相邻项的边界框彼此没有重叠。 Alice 将音译规则形式化如下。

让 f 是音译功能。

每个序列 s = t_1 t_2 ... t_m 可以从左到右书写,也可以从右到左书写。 不过这里请注意 t_1 对应于句子中最左边的术语, t_2 到左侧第二项,依此类推。

让我们定义一下 ḡ 是翻转的字形 g。 当序列包含一个或多个不翻转就无法读取的单字形术语(即存在一个整数)时,必须从右向左写入序列 i 其中 t_i 是单个字形 g,和 g 不在单独给出的字形字典中,而 ḡ 是。 在这种情况下 f(s) 定义为 f(t_m) f(t_{m-1}) ... f(t_1),否则 f(s) = f(t_1) f(t_2) ... f(t_m)。 如果存在一个或多个不翻转就无法读取的字形,则保证序列中的所有字形都被翻转。

如果术语 t_i 是一个包含序列的框 s', f(t_i) = [ f(s') ]。 如果术语 t_i 是一个字形 g, f(t_i) 映射到与字形对应的字母 g,或 ḡ 如果序列包含 g 从右向左书写。

请制作一个程序来音译巨石上的句子来帮助爱丽丝。


输入

输入由多个数据集组成。 输入的末尾由两个由单个空格分隔的零表示。

每个数据集都具有以下格式。

n m
glyph_1
...
glyph_n
string_1
...
string_m

n (1\leq n\leq 26) 是字形数量, m (1\leq m\leq 10) 是整体的数量。 glyph_i 由以下格式给出。

c h w
b_{11}...b_{1w}
...
b_{h1}...b_{hw}

c 是 Alice 分配给字形的小写字母。 h 和 w (1 \leq h \leq 15, 1 \leq w \leq 15) 分别指定字形位图的高度和宽度。 矩阵 b 表示位图。 白细胞表示为 . 黑色单元格表示为 *.

您可以假设所有字形都分配有不同的字符。 您可以假设位图的每一列都包含至少一个黑色单元,并且位图的第一行和最后一行包含至少一个黑色单元。 每个位图彼此不同,但翻转的位图可能与另一个位图相同。 此外,可能存在对称位图。

string_i 由以下格式给出。

h w
b_{11}...b_{1w}
...
b_{h1}...b_{hw}

h 和 w (1 \leq h \leq 100, 1 \leq w \leq 1000) 是序列位图的高度和宽度。 与字形字典类似, b 表示位图,其中白色单元格表示为 . 和一个黑色电池 *.

没有噪音:位图中的每个黑色单元格属于一个字形或一个矩形框。 矩形的高度至少为 3 且大于最高字形的最大高度。 矩形的宽度至少为 3。

框的边缘周围必须有 1 个像素的边距。

您可以假设字形永远不会垂直排列。 此外,您可以假设如果两个矩形或一个矩形和一个字形位于同一列中,则其中一个包含另一个。 对于所有字形边界框和矩形黑色单元,每两个之间至少有一个白色单元。 您可以假设位图中至少有一个单元格是黑色的。

输出

对于每个巨石,在一行中输出音译的句子。 输出一个数据集后,输出 # 一行。


示例输入

2 1
a 11 9
****.....
.*.*.....
.*.*.....
.*..*....
.**..*...
..**..*..
..*.*....
..**.*.*.
..*..*.*.
..*****.*
******.**
b 10 6
....*.
....*.
....*.
....*.
....*.
....*.
....*.
....*.
.**..*
*****.
19 55
*******************************************************
*.....................................................*
*.********************.********************...........*
*.*..................*.*..................*...........*
*.*.****.............*.*.............****.*.****......*
*.*..*.*..........*..*.*..*..........*.*..*..*.*......*
*.*..*.*..........*..*.*..*..........*.*..*..*.*......*
*.*..*..*.........*..*.*..*.........*..*..*..*..*.....*
*.*..**..*........*..*.*..*........*..**..*..**..*....*
*.*...**..*.......*..*.*..*.......*..**...*...**..*...*
*.*...*.*.........*..*.*..*.........*.*...*...*.*.....*
*.*...**.*.*......*..*.*..*......*.*.**...*...**.*.*..*
*.*...*..*.*......*..*.*..*......*.*..*...*...*..*.*..*
*.*...*****.*..**..*.*.*.*..**..*.*****...*...*****.*.*
*.*.******.**.*****..*.*..*****.**.******.*.******.**.*
*.*..................*.*..................*...........*
*.********************.********************...........*
*.....................................................*
*******************************************************
2 3
a 2 3
.*.
***
b 3 3
.*.
***
.*.
2 3
.*.
***
4 3
***
*.*
*.*
***
9 13
************.
*..........*.
*.......*..*.
*...*..***.*.
*..***.....*.
*...*......*.
*..........*.
************.
.............
3 1
a 2 2
.*
**
b 2 1
*
*
c 3 3
***
*.*
***
11 16
****************
*..............*
*....*********.*
*....*.......*.*
*.*..*.***...*.*
*.**.*.*.*.*.*.*
*....*.***.*.*.*
*....*.......*.*
*....*********.*
*..............*
****************
0 0

样本输入的输出

[[ab][ab]a]
#
a
[]
[ba]
#
[[cb]a]
#