← 返回题目列表

Codeforces · 1280/F

F. 星际滑动拼图

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

你是一名星际外科医生,你有一名外星病人。为了解决这个问题,我们可以并且将使用 $$$2 \times (2k + 1)$$$ 矩形网格来建模该患者的身体。外星人有 $$$4k + 1$$$ 不同的器官,编号为 $$$1$$$ 到 $$$4k + 1$$$。

在健康的外星人中,器官以特定的方式排列。例如,以下是从顶部观察时,健康的外星人的器官的位置,$$$k = 4$$$:

这里,E 代表空白区域。

一般来说,第一行包含器官 $$$1$$$ 到 $$$2k + 1$$$ (按从左到右的顺序),第二行包含器官 $$$2k + 2$$$ 到 $$$4k + 1$$$ (按从左到右的顺序),然​​后是后面的空白。

你的病人的器官是完整的,并且在他们的体内,但他们不知何故被洗牌了!作为一名星际外科医生,你的工作就是将一切放回正确的位置。在整个过程中,外星人的所有器官都必须在其体内。这意味着在该过程的任何时刻,(网格中)只有一个单元格是空的。此外,您只能通过执行以下操作之一来移动器官:

- 你可以将任何器官的空白E的位置切换到其紧邻的左侧或紧邻的右侧(如果存在)。实际上,您可以通过将有问题的器官滑到空白处来做到这一点;
- 仅当空白区域位于最左列、最右列或最中心列时,您才可以将任何器官的空白区域 E 的位置切换到其直接顶部或直接底部(如果存在)。同样,您可以通过将有问题的器官滑到空白处来完成此操作。

你的工作是找出在手术过程中必须执行的一系列动作,以便将患者的所有 $$$4k + 1$$$ 内脏器官放回正确的细胞中。如果不可能这样做,你必须这么说。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 4$$$) 表示测试用例的数量。接下来的几行包含测试用例的描述。

每个测试用例由三行组成。第一行包含一个整数 $$$k$$$ ($$$1 \le k \le 15$$$),它确定网格的大小。然后是两行。它们每个都包含 $$$2k + 1$$$ 空格分隔的整数或字母 E。它们分别描述第一行和第二行器官。保证所有 $$$4k + 1$$$ 器官都存在,并且恰好有一个 E。

输出

对于每个测试用例,首先打印一行,其中包含:

- 如果可以将所有内脏器官放回正确位置,则手术完成;
- 如果不可能,手术就会失败。

如果不可能,那么这是测试用例的唯一输出行。但是,如果可能的话,再输出几行,描述将器官放置在正确位置的移动顺序。

移动序列将是一个(可能是空的)字母 u、d、l 或 r 字符串,表示将位于空白区域正上方、下方、左侧或右侧的器官分别滑入空白区域。将下一行中的移动顺序打印为字符串。

为了方便起见,您可以使用快捷方式来减小输出的大小。您可以使用大写字母作为移动序列的快捷方式。例如,您可以选择 T 来表示字符串 lddrr。这些快捷方式还可能包含其他快捷方式!例如,您可以选择E代表TruT等。

您可以使用任意数量的大写字母(包括没有)作为快捷方式。唯一的要求如下:

- 单个案例输出中所有字符串的总长度最多为 $$$10^4$$$;
- 不得存在涉及可从主序列到达的快捷方式的循环;
- 展开所有快捷方式后,最终的移动序列是有限的。请注意,最终的移动序列(展开后)可能比 $$$10^4$$$ 长得多;唯一的要求是它是有限的。

例如,如果 T = lddrr、E = TruT 且 R = rrr,则 TurTlER 扩展为:

- 图特尔
- lddrrurTlER
- lddrrurlddrrlER
- lddrrurlddrrlTruTR
- lddrrurlddrrllddrrruTR
- lddrrurlddrrllddrrrulddrrR
- lddrrurlddrrllddrrrulddrrrrrr

要使用快捷方式,请将每个快捷方式打印为大写字母,然后是空格,然后是该快捷方式代表的字符串。它们可以按任何顺序打印。在所有这些的末尾,打印一行包含 DONE 的内容。

注意:即使您不打算使用快捷方式,您仍然需要打印 DONE。

您的序列不必是最短的。任何有效的移动序列(满足上述要求)都将被接受。

示例

输入 #1

2
3
1 2 3 5 6 E 7
8 9 10 4 11 12 13
11
34 45 6 22 16 43 38 44 5 4 41 14 7 29 28 19 9 18 42 8 17 33 1
E 15 40 36 31 24 10 2 21 11 32 23 30 27 35 25 13 12 39 37 26 20 3

输出 #1

SURGERY COMPLETE
IR
R SrS
S rr
I lldll
DONE
SURGERY FAILED

注意

第一个示例输出中定义了三个快捷方式:

- R = SrS
- S = rr
- I = lldll

移动顺序是 IR,它扩展为:

- 红外
- lldllR
- lldllSrS
- lldllrrrS
- lldllrrrrr