AT_tenka1_2013_qualB_d 天下一二三パズル リベンジ
题目描述
尤塔觉得 15 拼图游戏太简单，所以把它改造成了一个更大的版本。然而，这样的困难程度对世界级程序员尤塔来说仍然不够。
新拼图在一个 $12 \times 12$ 的棋盘上进行，其中有编号为 $1$ 到 $123$ 的独立方块，共计 123 个，还有 21 个空白格。你的任务是通过将这些数字方块向上、向下、向左或向右滑动，来把初始配置变为完成状态。
请说明解决这个 123 拼图的步骤。
### 初始配置
棋盘的初始状态如下图所示（图 1）。
### 完成图
拼图的完成状态如下图所示（图 2）。
在完成图中，第 $i$ 行第 $j$ 列的方块必须满足以下条件：
- 如果 $12 \times (i-1) + j \leq 123$，则该位置上放有编号为 $12 \times (i-1) + j$ 的方块。
- 如果 $12 \times (i-1) + j > 123$，则该位置是空白的。
### 得分规则
每移动一次方块计为一步，记录步数为 $N$，得分 $S$ 由下面的公式计算：
\[ S = 200 - \text{floor}(N / 40) \]
其中，$\text{floor}(x)$ 是不大于 $x$ 的最大整数。
例如，若用 1999 步完成，则得分为 151 分。
以下情形得分为 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 P1 D1 P2 D2 ... PN DN
```
其中，$N$ 是步骤总数，每一步 $P_i$ 代表要移动的方块编号，$D_i$ 是移动方向，方向可以是 `up`、`down`、`left` 或 `right`。操作完成后棋盘必须达到完成状态。
例如，初始棋盘：
```
0 1
2 3
```
如果进行以下移动：
```
1 left
3 up
2 right
```
棋盘将变为：
```
1 3
0 2
```
请在输出的最后加上换行符。你可以事先计算好步骤然后直接提交结果。在这种情况下，请选择使用 Text(cat) 语言进行提交。
**本翻译由 AI 自动生成**
输入格式
无
输出格式
无