AT_ahc059_a [AHC059A] Stack to Match Pairs

$ N\times N $ マスの盤面がある。 一番左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス移動した先のマスの座標を $ (i,j) $ とする。 $ N $ は偶数であり、 $ 0 $ から $ \frac{N^2}{2}-1 $ までの番号が書かれたカードがそれぞれ $ 2 $ 枚ずつある。 初期状態では、これらのカードが各マスにちょうど1枚ずつ置かれている。 あなたは初期状態で位置 $ (0,0) $ に空の山札を持った状態から開始し、以下の操作を繰り返す。 1. 現在位置の上下左右に隣接するマスに移動する。 $ N\times N $ マスの外部に出ることはできない。 2. 現在位置にカードがある場合、そのカードを山札の一番上に移動させることができる。これにより山札の上から2枚のカードの番号が一致した場合、それら2枚を山札から取り除く。 3. 現在位置にカードがない場合、山札の一番上のカードを現在位置に置くことができる。山札が空である場合や、現在位置にすでにカードがある場合には、この操作は行えない。 操作は最大で $ 2N^3 $ 回行うことができる。 最終的にすべてのカードを盤面および山札から取り除きたい。 **移動回数** ができるだけ少ない操作手順を求めよ。 操作2および3の回数は操作回数の上限には含まれるが、評価には含まれないことに注意せよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_{0,0} $ $ \cdots $ $ a_{0,N-1} $ $ \vdots $ $ a_{N-1,0} $ $ \cdots $ $ a_{N-1,N-1} $ - すべてのテストケースにおいて、 $ N = 20 $ に固定されている。 - $ a_{i,j} $ は初期状態でマス $ (i,j) $ に置かれているカードに書かれた番号を表し、 $ 0\leq a_{i,j}\leq \frac{N^2}{2}-1 $ を満たす整数である。 - 同じ値の $ a_{i,j} $ はちょうど2つ存在する。

$ t $ ターン目の操作を、1文字 $ c_t $ で以下のように表す。 1. 操作1(移動)を行う場合：移動方向に応じて、上：`U`、下：`D`、左：`L`、右：`R` 2. 操作2(取る)を行う場合：`Z` 3. 操作3(置く)を行う場合：`X` 操作回数を $ T $ としたとき、以下の形式で標準出力に出力せよ。 > $ c_0 $ $ \vdots $ $ c_{T-1} $ [例を見る](https://img.atcoder.jp/ahc059/b8ckwh7N.html?lang=ja&seed=0&output=sample)

### 得点 出力した操作列における移動回数を $ K $ 、最終的に盤面および山札に残っているカードの枚数を $ X $ としたとき、以下の得点が得られる。 - $ X=0 $ の場合、 $ N^2+2N^3-K $ - $ X>0 $ の場合、 $ N^2-X $ 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 カードの初期配置 $ a_{i,j} $ は $ N^2 $ 枚のカードをランダムな順に並び替えることで生成される。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc059/b8ckwh7N.html?lang=ja): ローカル版より高性能でアニメーション表示と手動プレイが可能です。 - [ローカル版](https://img.atcoder.jp/ahc059/b8ckwh7N.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc059/b8ckwh7N_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。