AT_ahc052_a [AHC052A] Single Controller Multiple Robots

AtCoder社の高橋社長は、オフィス環境改善のため、最新式のワックスがけロボットを複数台導入した。 これでオフィスの床がピカピカになると安心したのも束の間、重大な問題が発覚した。 操作に必要なコントローラーをたった一つしか注文していなかったのである。 通常であれば絶望的な状況だが、幸いにもそのコントローラーは高度な「キーコンフィグ」機能を備えていた。 各ボタンに対して、ロボットごとに個別の行動を設定できる高機能な装置である。 高橋社長は、あなたにこの難題の解決を依頼した。 限られた手段を駆使して、オフィス全体の床に効率よくワックスがけを行ってほしい。

$ N\times N $ マスのオフィスがある。 左上のマスの座標を $ (0, 0) $ とし、下方向に $ i $ 、右方向に $ j $ 進んだ位置の座標を $ (i, j) $ とする。 $ N\times N $ マスの外周は壁で囲まれており、隣接するマス間にも壁が存在する場合がある。 $ M $ 台のロボットを使って、全てのマスにワックスがけを行いたい。 $ k $ 番目のロボットの初期位置は $ (i_k, j_k) $ であり、初期位置を含め、ロボットが一度でも移動したマスはワックスがけされたとみなされる。 すべてのロボットは一つのコントローラーで同時に操作される。 このコントローラーには $ K $ 個のボタンがあり、ワックスがけを開始する前に、各ボタンと各ロボットの組に対して、上下左右の隣接マスへの移動、またはその場での待機の計 $ 5 $ 通りの行動のうちいずれかを設定しておく。 ボタンを押すと、全てのロボットが同時に対応する行動を実行する。 ボタンごとの設定はロボットごとに異なってよく、たとえば「ボタン 0 でロボット 0 は上に移動し、ロボット 1 は下に移動する」といった設定が可能である。 ワックスがけの開始後にボタンの割当を変更することはできない。 ロボットが移動しようとしたとき、移動先との間に壁がある場合、そのロボットはその場にとどまる。 ロボット同士は互いに干渉せず、同じマスに複数のロボットが存在してもよい。 操作は最大で $ 2N^2 $ 回まで行うことができる。 ボタンの割当と操作順を工夫することで、できるだけ少ない操作回数で全てのマスにワックスがけを施してほしい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ i_0 $ $ j_0 $ $ \vdots $ $ i_{M-1} $ $ j_{M-1} $ $ v_{0,0} \cdots v_{0,N-2} $ $ \vdots $ $ v_{N-1,0} \cdots v_{N-1,N-2} $ $ h_{0,0} \cdots h_{0,N-1} $ $ \vdots $ $ h_{N-2,0} \cdots h_{N-2,N-1} $ - 全てのテストケースにおいて、 $ N=30 $ 、 $ M=10 $ 、 $ K=10 $ に固定されている。 - $ (i_k, j_k) $ は $ k $ 台目のロボットの初期位置を表し、全ての初期位置は互いに異なる。 - $ v_{i,0} \cdots v_{i,N-2} $ は長さ $ N-1 $ の `01` からなる文字列であり、 $ j $ 文字目 $ v_{i,j} $ はマス $ (i, j) $ とマス $ (i, j+1) $ の間に壁がある（`1`）かない（`0`）かを表す。 - $ h_{i,0} \cdots h_{i,N-1} $ は長さ $ N $ の `01` からなる文字列であり、 $ j $ 文字目 $ h_{i,j} $ はマス $ (i, j) $ とマス $ (i+1, j) $ の間に壁がある（`1`）かない（`0`）かを表す。 - 全てのマスは互いに到達可能であることが保証されている。

まず、ボタンの割当を以下の形式で標準出力に出力せよ。 > $ c_{0,0} $ $ \cdots $ $ c_{0,M-1} $ $ \vdots $ $ c_{K-1,0} $ $ \cdots $ $ c_{K-1,M-1} $ ここで、 $ c_{i,j} $ は $ i $ 番目のボタンを押した際に $ j $ 番目のロボットが取る行動を表す 1 文字であり、次の 5 種類のいずれかである。 - `U`: 上方向に 1 マス移動 - `D`: 下方向に 1 マス移動 - `L`: 左方向に 1 マス移動 - `R`: 右方向に 1 マス移動 - `S`: その場にとどまる その後、操作列を以下の形式で出力する。 > $ a_0 $ $ \vdots $ $ a_{T-1} $ ここで、 $ a_t $ は $ t $ ターン目に押すボタンを表す $ 0 $ 以上 $ K-1 $ 以下の整数値である。 [例を見る](https://img.atcoder.jp/ahc052/ZN1uhrbm.html?lang=ja&seed=0&output=sample)

### 得点 出力した操作列の長さを $ T $ （ $ T \leq 2N^2 $ ）、ワックスがけされなかったマスの個数を $ R $ としたとき、以下の得点が得られる。 - $ R = 0 $ の場合、 $ 3N^2 - T $ - $ R > 0 $ の場合、 $ N^2 - R $ 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ \mathrm{rand}(L, U) $ を、 $ L $ 以上 $ U $ 以下の整数値を一様ランダムに生成する関数とする。 $ M $ 台のロボットの初期位置は、 $ N^2 $ 個の座標から、相異なる $ M $ 個を一様ランダムに生成することにより決定する。 壁は以下の操作を $ 5 $ 回繰り返すことにより生成される。 1. 壁を生成する方向を上下左右からランダムに決定する。 2. 壁の長さを $ L = \mathrm{rand}(10, 20) $ により生成する。 3. 縦方向の壁の場合、始点 $ (i, j) $ を $ i = \mathrm{rand}(5, N-5),\ j = \mathrm{rand}(4, N-6) $ により選択する。ただし、これまでに生成された縦壁に使用された $ j $ と絶対値の差が $ 4 $ 以下の $ j $ が選ばれた場合は、方向の選択からやり直す。 上方向の場合は $ v_{i-L+1, j}, \cdots, v_{i, j} $ を、下方向の場合は $ v_{i, j}, \cdots, v_{i+L-1, j} $ を `1` に設定する。ただし、盤面外にはみ出した部分は無視する。 4. 横方向の壁の場合、始点 $ (i, j) $ を $ i = \mathrm{rand}(4, N-6),\ j = \mathrm{rand}(5, N-5) $ により選択する。ただし、これまでに生成された横壁に使用された $ i $ と絶対値の差が $ 4 $ 以下の $ i $ が選ばれた場合は、方向の選択からやり直す。 左方向の場合は $ h_{i, j-L+1}, \cdots, h_{i, j} $ を、右方向の場合は $ h_{i, j}, \cdots, h_{i, j+L-1} $ を `1` に設定する。ただし、盤面外にはみ出した部分は無視する。 5. 生成した壁に対し、すべてのマスが到達可能であるかを判定する。到達不能な場合は壁を初期化し、 $ 5 $ 回の反復をやり直す。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc052/ZN1uhrbm.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc052/ZN1uhrbm.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc052/ZN1uhrbm_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。