AT_ahc042_a [AHC042A] Oni wa Soto, Fuku wa Uchi

本日 2月2日、日本では**節分**という伝統行事が行われる。 節分は、季節の変わり目に邪気を払い、福を招くための行事であり、人々は 「鬼は外！」 と唱えながら炒った豆をまいて邪気（鬼）を追い払い、「福は内！」 と唱えながら福を招き入れる。 高橋くんは、そんな節分にちなんだ「鬼は外福は内ボードゲーム」を遊んでいる。 このゲームでも、鬼を追い払い、福を呼び込むことが目的である。 できるだけ高得点を獲得するような手順を求めて欲しい。

$ N \times N $ のマス目からなる盤面がある。 一番左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 マス $ (i,0),(i,1),\cdots,(i,N-1) $ を **行 $ i $** 、マス $ (0,j),(1,j),\cdots,(N-1,j) $ を **列 $ j $** と呼ぶ。 初期状態では、盤面上に **鬼**  と **福**  の駒がそれぞれ $ 2N $ 個ずつ、全て異なるマスに存在している。 あなたは 1 回の操作で行または列を 1 つ選び、選んだ行/列を、左右/上下のいずれかの方向に 1 マスだけ動かすことが出来る。 - 行 $ i $ を左方向に動かす: マス $ (i,0) $ にある駒は盤面から取り除かれ、各 $ j=1, \dots, N-1 $ に対し、マス $ (i,j) $ にある駒は $ (i,j-1) $ に移動する。 - 行 $ i $ を右方向に動かす: マス $ (i,N-1) $ にある駒は盤面から取り除かれ、各 $ j=0, \dots, N-2 $ に対し、マス $ (i,j) $ にある駒は $ (i,j+1) $ に移動する。 - 列 $ j $ を上方向に動かす: マス $ (0,j) $ にある駒は盤面から取り除かれ、各 $ i=1, \dots, N-1 $ に対し、マス $ (i,j) $ にある駒は $ (i-1,j) $ に移動する。 - 列 $ j $ を下方向に動かす: マス $ (N-1,j) $ にある駒は盤面から取り除かれ、各 $ i=0, \dots, N-2 $ に対し、マス $ (i,j) $ にある駒は $ (i+1,j) $ に移動する。 操作は最大で $ 4N^2 $ 回まで行うことができる。 あなたの目的は、できるだけ少ない操作回数で、福を一つも取り除くことなく、盤面上のすべての鬼を取り除くことである。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C_0 $ $ \vdots $ $ C_{N-1} $ - 盤面の大きさ $ N $ は 全てのテストケースで $ N=20 $ に固定されている。 - 各 $ i=0,1,\cdots,N-1 $ に対し、 $ C_i $ は行 $ i $ の初期状態を表す長さ $ N $ の文字列であり、その $ j $ 文字目は、次のいずれかで表される。 - `x`: 鬼が存在する - `o`: 福が存在する - `.`: 鬼も福も存在しない - 鬼と福の個数はそれぞれ $ 2N $ である。 - **初期状態で鬼が存在する各マスについて、次のいずれかの条件を満たすことが保証されている。これにより、盤面上のすべての鬼を取り除き、すべての福を残すような、 $ 4N^2 $ 手以下の操作手順が必ず存在する。** - 同じ列の上方向にあるすべてのマスに福が存在しない。 - 同じ列の下方向にあるすべてのマスに福が存在しない。 - 同じ行の左方向にあるすべてのマスに福が存在しない。 - 同じ行の右方向にあるすべてのマスに福が存在しない。 #### ヒント 鬼が存在するマス $ (i,j) $ について、上方向に福が存在しない場合、上方向の操作を $ i+1 $ 回、下方向の操作を $ i+1 $ 回行うと、福を一つも取り除くことなく鬼 $ (i,j) $ を取り除くことが出来る。 同様に、下・左・右の各方向に福が存在しない場合も、対応する操作を行うことで鬼を取り除くことができる。 この操作を行う前後で盤面上に残る駒の位置は変化しないため、すべての鬼に対してこの操作を適用することで、福を一つも取り除くことなく、すべての鬼を取り除くことが可能である。

$ t $ 手目の操作を以下のようにして方向を表す文字 $ d_t $ と行・列の番号を表す数値 $ p_t $ の組 $ (d_t, p_t) $ で表す。 - 行 $ i $ を左方向に動かす: (`L`, $ i $ ) - 行 $ i $ を右方向に動かす: (`R`, $ i $ ) - 列 $ j $ を上方向に動かす: (`U`, $ j $ ) - 列 $ j $ を下方向に動かす: (`D`, $ j $ ) このとき、以下の形式で標準出力に出力せよ。 > $ d_0 $ $ p_0 $ $ \vdots $ $ d_{T-1} $ $ p_{T-1} $ 出力の操作回数 $ T $ は $ 4N^2 $ 以下でなければならない。 上限を超えた場合、WA と判定される。 [例を見る](https://img.atcoder.jp/ahc042/cnhLtdRT.html?lang=ja&seed=0&output=sample)

### 得点 出力した操作列における操作回数を $ T $ 、最終的に盤面上に残る鬼の個数を $ X $ 、盤面から取り除かれた福の個数を $ Y $ とする。 このとき、以下の得点が得られる。 - $ X=Y=0 $ の場合、 $ 8N^2 - T $ - $ X>0 $ または $ Y>0 $ の場合、 $ 4N^2 - N (X+Y) $ 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 まず、 $ N^2 $ 個のマスの中から異なる $ 2N $ マスをランダムに選び、 $ 2N $ 個の福の駒の位置を決定する。 次に、次のいずれかの条件を満たすマスを列挙し、これを $ S $ とする。 - 同じ列の上方向にあるすべてのマスに福が存在しない。 - 同じ列の下方向にあるすべてのマスに福が存在しない。 - 同じ行の左方向にあるすべてのマスに福が存在しない。 - 同じ行の右方向にあるすべてのマスに福が存在しない。 もし $ S $ の要素数が $ 2N $ より小さい場合、福の生成をやり直す。 最後に、 $ S $ からランダムに $ 2N $ 個のマスを選び、鬼の駒の位置を決定する。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc042/cnhLtdRT.html?lang=ja): ローカル版より高性能でアニメーション表示と手動プレイが可能です。 - [ローカル版](https://img.atcoder.jp/ahc042/cnhLtdRT.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc042/cnhLtdRT_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。