/ 
Time Limit: 8 sec / Memory Limit: 256 MB
問題文
ユウタ君は15パズルと呼ばれるスライドパズルを遊んでいたが簡単すぎて飽きてしまったため、15パズルを大きいサイズに改造してしまった。それでも天下一級のプログラマのユウタ君には簡単すぎたらしく、唖然としてしまった。
改造されたパズルは、12 \times 12 マスの盤面に対して 1 ～ 123までの整数が書かれた 1 \times 1 マスの正方形のピースが 123 個と空白が 21 個配置されている123パズルだった。そして、整数の書かれたピースを、上下左右の空白のマスにスライドさせて、下記の初期配置から完成図にするのが目的である。
この123パズルを解く手順を答えなさい。
初期配置
盤面の初期状態は以下の通りである（図 1）。
完成図
盤面の完成図は以下の通りである（図 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 番目の整数は、123パズルにおいて、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)を選択して提出すること。