问题陈述
有一天,爱丽丝在森林里发现了一块古老的巨石。
她调查了巨石,发现这是用古老语言写的句子。 句子由字形和围绕它们的矩形组成。 对于上面的示例,有以下字形。
请注意,句子中的某些字形会水平翻转。
她决定使用 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] #