#P4790. [CERC2016]Dancing Disks
[CERC2016]Dancing Disks
[CERC2016] 舞动的盘子 Dancing Disks
题目描述
Luka 熟悉汉诺塔,发明了一种使用盘子和柱子的游戏。有 个大小互不相同的盘子,按大小从小到大编号为 至 。 根柱子排成 行 列,行号从上到下、列号从左到右均为 至 。

初始时,所有盘子叠在左上角 的柱子上。每一步任选一根柱子,从顶部取下一叠盘子,至少取一个,再把整叠盘子原顺序放在其正下方或正右方相邻柱子的顶部。
目标是把全部盘子移到右下角 的柱子上,并使它们从顶到底按大小递增。保证存在解,给出任意一种合法操作序列。
输入格式
第一行一个整数 。第二行 个整数 ,按从底到顶的顺序给出左上角柱子上的盘子编号。这 个编号互不相同,且都在 内。
输出格式
每步输出一行 r c p k。 是取盘子的柱子的行、列编号,均在 内。 为 D 或 R,分别表示向下或向右移动到相邻柱子。 为正整数,表示移动该柱顶部的盘子数。
按执行顺序逐行输出所有步骤。所有步骤都必须合法且最终达到目标。
数据范围
。
样例 #1
样例输入 #1
6
1 6 5 4 3 2
样例输出 #1
1 1 D 6
2 1 D 6
3 1 D 6
4 1 D 6
5 1 D 6
6 1 R 6
6 2 R 6
6 3 R 6
6 4 R 6
6 5 R 5
6 5 R 1
样例说明
前九步把整叠盘子移到 ,盘子的顺序未改变。第十步把顶部五个盘子整体移到目标柱,这五个盘子从底到顶为 。最后再放上编号为 的盘子。