← 返回题目列表

AtCoder · tenka1_2013_qualB_d

D. 天海一文桑拼图复仇

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

問題文

Yuta正在玩一款名为15 Puzzle的幻灯片拼图,但他厌倦了它,因为它太简单了,所以他将15 Puzzle修改为更大的尺寸。尽管如此,对于世界级程序员裕太君来说,这似乎太容易了,他感到震惊。

修改后的拼图是12 \times 12 对着方板 已写入 1 ~ 123以内的整数 1 \times 1 正方形的正方形块是 123 块和空格是 共有 123 个谜题,排列成 21 块。目标是将写有整数的棋子滑到顶部、底部、左侧和右侧的空白方块上,以根据如下所示的初始排列创建完整的绘图。

请告诉我解决这个123谜题的步骤。

初期配置

板子的初始状态如下(图2) 1)。

図 1 初期配置

完成図

完成后的板面如下(图2) 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) 作为要使用的语言并提交。