問題文
Yuta正在玩一款名为15 Puzzle的幻灯片拼图,但他厌倦了它,因为它太简单了,所以他将15 Puzzle修改为更大的尺寸。尽管如此,对于世界级程序员裕太君来说,这似乎太容易了,他感到震惊。
修改后的拼图是12 \times 12 对着方板 已写入 1 ~ 123以内的整数 1 \times 1 正方形的正方形块是 123 块和空格是 共有 123 个谜题,排列成 21 块。目标是将写有整数的棋子滑到顶部、底部、左侧和右侧的空白方块上,以根据如下所示的初始排列创建完整的绘图。
请告诉我解决这个123谜题的步骤。
初期配置
板子的初始状态如下(图2) 1)。
完成図
完成后的板面如下(图2) 2)。
在完成的图中,i 线 j 第二个方块是
- 12 \times (i-1) + j \leq 123是一个整数 有一块上面写着12 \times (i-1) + j。
- 12 \times (i-1) + j > 123为空
变为。
配点
1 垂直和水平移动一件。 1 移动一个正方形 1 作为手,移动的步数 评分者: N 得分为 S 由下式确定。 表示不超过
S = 200 - {\rm floor}(N / 40)
※{\rm floor}(x) 计算x的最大整数。
例如 1999 如果您亲手完成了绘图, 151 点。
但是,
- 如果上式为负数
- 给出无法实现的输出时
- 当给出的输出未达到完成图时
是 给出了 0 点。
入力
以下表示初始配置的文本来自标准输入。
i 写在行中
第 j 个整数是i 从该行的左侧开始 j 表示方格内棋子上所写的整数,0 代表空格。
85 117 83 31 61 55 35 67 28 60 22 52 97 78 51 1 105 121 62 0 96 119 19 2 109 92 57 86 59 76 21 32 0 5 46 8 4 72 106 0 81 0 0 90 115 120 45 48 95 0 23 82 24 87 114 0 93 0 6 20 43 116 77 0 15 38 37 63 69 40 33 0 0 100 64 0 122 68 75 118 111 26 104 53 112 99 3 73 98 108 12 0 58 49 0 65 74 66 88 56 39 70 0 102 0 94 101 107 41 103 36 50 10 34 0 14 7 89 0 27 113 91 25 71 79 80 42 0 29 17 47 54 123 110 0 13 30 84 9 11 16 18 0 44
出力
按照以下格式输出从初始布局到完成的图纸的步骤。
N P_1 D_1 P_2 D_2 ... P_N D_N
N代表移动次数,
P_i, D_i 是
给出了 i表示要移动的棋子以及移动的方向。
1 \leq P_i \leq 123必须是D_i是
给出了up, down, left, right 之一。
另外,请遵循输出程序N当你移动你的手时,棋盘必须是一张完整的图画。
在
例如,
0 1 2 3董事会上 如果移动步骤
1 left 3 up 2 right如果你移动脚步
1 3 0 2变为。
请在输出末尾添加换行符。
您也可以将预先计算输出的结果原样提交。在这种情况下,请选择 Text(cat) 作为要使用的语言并提交。