#539. 「习题3-5」 谜题(Puzzle, ACM/ICPC World Finals 1993) 暂未评定

原题链接

30年前流行的一种儿童益智游戏由一个5×5的框架组成，其中包含24个小号大小相等的正方形。每一个小方块上都印着字母表上的一个独特的字母。从那以后 画面内只有24个方格，画面中还有一个空位，也是一样的大小如一个小正方形。一个正方形可以移动到那个空位置，如果它是立即到右、左、上或下空位置。拼图的目的是滑动方块使框架按字母顺序显示字母。

下面的插图展示了一个在其原始配置和之后的配置中的谜题
以下6个动作的顺序：
1） 空位置上方的方块移动。

2） 空位置右侧的方块移动。

3） 空位置右侧的方块移动。

4） 空位置下方的方块移动。

5） 空位置下方的方块移动。

6） 空位置左侧的方块移动。

程序的输入由多个谜题组成。每个谜题由它的初始构型和谜题的移动顺序来描述。 每个谜题描述的前5行是起始构型。后面的行给出了移动的顺序。

棋格显示的第1行对应于谜题中最上面一行的方块。其他行按顺序排列。棋格中的空位用空白表示。每个显示行包含5个字符，从最左边的方格上的字符开始（如果最左边的方格实际上是空的框架位置，则为空白）。这些显示线将对应一个合法的谜题。

移动的顺序用As、Bs、Rs和Ls的序列来表示哪个方格移动到空格位置。A表示空位置上方的位置移动；B表示空位置下方的位置移动；L表示空位置左边的位置移动；R表示空位置右边的位置移动。即使用4个移动字符中的一个来表示，也有可能出现非法移动。如果出现了非法移动，那么这个谜题就被认为是没有规则的。这个移动的序列可能会分布在几行中，但它总是以数字0结束。数据的结束用字符Z表示。

每个谜题的输出都以一个适当的标签号码开始（谜题#1，谜题#2，等等）。如果谜题没有最终答案，那么后面会有一条信息。否则，将显示该谜题的名称。

将每一行的nal con guration格式化，使两个相邻的字母之间有一个空白字符。将空方格与字母一样对待。例如，如果空白是一个内部位置，那么它将显示为3个空白的序列，一个用于分隔左边的方块，一个用于空位置本身，一个用于分隔右边的方块。

用一个空行将不同拼图记录的输出分开。

注：样本输入的第一条记录对应于上面的谜题。

样例输入

TRGSJ
XDOKI
M VLN
WPABE
UQHCF
ARRBBL0
ABCDE
FGHIJ
KLMNO
PQRS
TUVWX
AAA
LLLL0
ABCDE
FGHIJ
KLMNO
PQRS
TUVWX
AAAAABBRRRLL0
Z

样例输出

Puzzle #1:
T R G S J
X O K L I
M D V B N
W P A E
U Q H C F

Puzzle #2:
A B C D
F G H I E
K L M N J
P Q R S O
T U V W X

Puzzle #3:
This puzzle has no final configuration.