AT_tenka1_2013_qualB_d 天下一二三パズル リベンジ

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

N/A

N/A