问题陈述
您有一块矩形板,分为多个正方形单元格。该板的行数和列数分别为 $3$ 和 $3 M + 1$,其中 $M$ 是正整数。行从上到下编号为 $1$ 到 $3$,列从左到右编号为 $1$ 到 $3 M + 1$。第 $i$ 行和第 $j$ 列的单元格用 $(i, j)$ 表示。
每个单元都是地板单元或墙壁单元。此外,列 $2, 3, 5, 6, \ldots, 3 M - 1, 3 M$ 中的单元格(形式为 $3 k - 1$ 或 $3 k$ 的数字,对于 $k = 1, 2, \ldots, M$)被涂上某种颜色。有 $26$ 颜色可用于绘画,编号为 $1$ 到 $26$。其他单元格(第 $1, 4, 7, \ldots, 3 M + 1$ 列)未绘制,每个单元格都是地板单元格。
您将要玩以下游戏。首先,您将一个令牌放在单元格 $(2, 1)$ 中。然后,您反复将其移动到相邻的楼层单元格。如果两个单元共享一条边,则它们被视为相邻。禁止将代币移至墙格或棋盘外。该游戏的目标是将代币移动到单元格 $(2, 3 M + 1)$。
对于这款游戏,您可以使用价值 26 美元的魔法开关!开关编号为 $1$ 到 $26$,每个开关对应于具有相同编号的颜色。当您按下开关 $x$ 时,每个涂有 $x$ 颜色的地板单元将成为一个墙壁单元,同时每个涂有 $x$ 颜色的墙壁单元将成为一个地板单元。
只有在开始移动令牌之前,您才可以按下一些神奇开关。确定是否存在一组可以推动的开关,以便您可以实现游戏的目标,如果存在,则找到这样的一组。
输入
输入是最多 $130$ 数据集的序列。每个数据集都以包含整数 $M$ 的行开始($1 \le M \le 1{,}000$)。以下三行代表棋盘,每行包含 $3 M + 1$ 个字符。第 $i$ 行中的第 $j$ 个字符描述了单元格 $(i, j)$ 的信息,如下所示:
第 $x$ 个大写字母表示单元格 $(i, j)$ 被涂成颜色 $x$,并且它最初是一个地板单元格。
第 $x$ 个小写字母表示单元格 $(i, j)$ 被涂成颜色 $x$,并且它最初是一个墙单元格。
一个句点 (
.) 表示单元格 $(i, j)$ 未绘制,因此它是地板单元格。
在这里,当且仅当该字符是句点时,您可以假设 $j$ 将为 $1, 4, 7, \ldots, 3 M + 1$ 之一。 输入的结尾由带有单个零的行表示。
输出
对于每个数据集,如果无法实现目标,则输出 $-1$。否则,以以下格式输出您为实现目标而按下的一组开关:
$n$ $s_1$ $s_2$ ... $s_n$
这里,$n$ 是您按下的开关数量,$s_1、s_2、\ldots、s_n$ 是与您按下的开关对应的大写字母,其中第 $x$ 个大写字母表示开关 $x$。这些大写字母$s_1、s_2、\ldots、s_n$ 必须是不同的,而它们的顺序并不重要。请注意,如果您不必按任何开关,则允许输出 $n = 0$(后面不带大写字母)。请参阅示例输出以获得说明。 如果有多个解,则输出其中任意一个。
示例输入
3 .aa.cA.Cc. .bb.Bb.AC. .cc.ac.Ab. 1 .Xx. .Yy. .Zz. 6 .Aj.fA.aW.zA.Jf.Gz. .gW.GW.Fw.ZJ.AG.JW. .bZ.jZ.Ga.Fj.gF.Za. 9 .ab.gh.mn.st.yz.EF.KL.QR.WA. .cd.ij.op.uv.AB.GH.MN.ST.XB. .ef.kl.qr.wx.CD.IJ.OP.UV.yz. 2 .AC.Mo. .IC.PC. .oA.CM. 20 .QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.qb. .qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb. .QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.qb. 0
样本输入的输出
3 B C E -1 3 J A G 10 A B G H M N S T Y Z 0 2 Q B