CF1280F Intergalactic Sliding Puzzle

你是一名星际外科医生，你有一位外星患者。为了解决这个问题，我们使用 $2 \times (2k+1)$ 的矩形网格来模型化这位患者的身体。外星人有 $4k+1$ 个不同的器官，编号从 $1$ 到 $4k+1$。 健康的外星人的器官排列方式是特定的。例如，这是一个健康的外星人的器官如从顶部看起来的样子 $k = 4$：（见原图） 其中，$E$ 表示空白（没有器官）。 通常情况下，第一行包含器官从左到右为 $1$ 到 $2k+1$。而第二行包含器官从左到右为 $2k+2$ 到 $4k+1$，然后是紧接着一个空白空间(即 “$E$” )。 你的患者的器官是完整的，并且位于他们的身体内部，但它们被以某种方式打乱了！作为一名星际外科医生，你的工作是将所有东西放回到正确的位置上。在整个过程中，外星人的所有器官都必须在身体内。这意味着在整个过程中，网格中恰好有且仅有一个单元格是空的。此外，你只能通过以下两种方式中的一种来移动器官： - 你可以将空白的空间 $E$ 与其左侧或右侧（如果存在）的任何器官交换位置。实际上，你可以将相应的器官滑动到空白的空间中来实现这一点； - 只有当空白的空间在最左侧列、最右侧列或正中间列上时，你才能将空白的空间 $E$ 与其上方或下方（如果存在）的任何器官交换位置。同样，你可以通过将相应的器官滑动到空白的空间中来实现这一点。 你的工作是在手术过程中找出一系列的移动步骤，来将全部的 $4k+1$ 个患者体内器官放回到正确的位置上。如果这样做是不可能的，你必须说明。 ### **简明题意** 给定一个 $2\times (2k + 1)$ 的数字矩阵图，请找出将每个数字都移回到初始位置的方法，若不可能，请说明。

第一行包含一个整数 $t$ $(1\le t\le 4)$，表示数据组数。接下来数行将会描述每组数据。 每组数据由三行组成。第一行包含一个整数 $k \ (1\le k\le 15)$，确定了网格的大小。接下来两行每行包含 $2k+1$ 个以空格分隔的整数或字母 $E$ 。它们分别描述了器官的第一行和第二行。保证所有的 $4k+1$ 个器官都存在，并且恰好有一个 $E$ (即恰好包含了 $1\sim 4k+1$ 和 “$E$”)。

对于每组数据，首先输出一行，包含以下内容之一： - 如果可以将所有的器官放回正确的位置，则输出 “$SURGERY \ COMPLETE$”； - 如果不可能则输出 “$SURGERY \ FAILED$”。 如果不可能，则只输出这一行。否则，输出接下来几行来描述移动的顺序。 将移动的顺序作为字符串输出在下一行。移动的顺序是一个字符串（可能为空），其中包含字母 $u$，$d$，$l$ 或 $r$ ，分别表示将位于空白空间上方、下方、左侧或右侧的器官滑动到空白空间。 为了方便起见，你可以使用更便捷的方式来缩小输出的规模。你可以使用大写字母作为移动序列的快捷方式。例如，你可以用 $T$ 来表示字符串 $lddrr$。这些快捷方式也可以包含其他的快捷方式！例如，你可以选择 $E$ 来表示 $TruT$（其中 $T$ 也是快捷方式）。 你可以使用任意数量的大写字母（也可以不用）作为快捷方式。但是要求如下： - 单组数据的输出中所有字符串的总长度最多为 $10^4$； - 禁止包含主序列可达的包含快捷方式的环（例如，下面这种是非法的：$A=RR,R=A$）； - 在展开所有快捷方式后，移动的结果序列必须是有限的。注意，最终的序列可能比 $10^4$ 长得多，但唯一要求的是它必须是有限的。 举个例子，如果 $T = lddrr$，$E = TruT$，$R = rrr$，则 $TurTlER$ 将展开为： - $TurTlER$ - $lddrrurTlER$ - $lddrrurlddrrlER$ - $lddrrurlddrrlTruTR$ - $lddrrurlddrrllddrrruTR$ - $lddrrurlddrrllddrrrulddrrR$ - $lddrrurlddrrllddrrrulddrrrrr$ 要使用快捷方式，请将每个快捷方式单独输出在一行上，以大写字母开头，然后是一个空格，然后是该快捷方式所代表的字符串。它们可以以任意顺序打印。在所有这些打印完之后，打印一行包含 $DONE$ 的单行。 **注意**：即使你没有使用快捷方式，你也需要打出 $DONE$。 你的序列不需要是最短的。只要满足上述要求的任何有效移动序列都算作正确。 ### **说明/提示** 样例中定义了三个快捷方式： - $R=SrS$ - $S=rr$ - $I=lldll$ 输出的移动序列为 $IR$，所以它展开后为： - $IR$ - $lldllR$ - $lldllSrS$ - $lldllrrrS$ - $lldllrrrrr$

There are three shortcuts defined in the first sample output: - R = SrS - S = rr - I = lldll The sequence of moves is IR and it expands to: - IR - lldllR - lldllSrS - lldllrrrS - lldllrrrrr