/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
ストーリー
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 回まで行うことができる。 ボタンの割当と操作順を工夫することで、できるだけ少ない操作回数で全てのマスにワックスがけを施してほしい。
得点
出力した操作列の長さを T（T \leq 2N^2）、ワックスがけされなかったマスの個数を R としたとき、以下の得点が得られる。
- R = 0 の場合、3N^2 - T
- R > 0 の場合、N^2 - R
合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。
入力
入力は以下の形式で標準入力から与えられる。
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 以下の整数値である。
入力生成方法
\mathrm{rand}(L, U) を、L 以上 U 以下の整数値を一様ランダムに生成する関数とする。
M 台のロボットの初期位置は、N^2 個の座標から、相異なる M 個を一様ランダムに生成することにより決定する。
壁は以下の操作を 5 回繰り返すことにより生成される。
- 壁を生成する方向を上下左右からランダムに決定する。
- 壁の長さを L = \mathrm{rand}(10, 20) により生成する。
- 縦方向の壁の場合、始点 (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に設定する。ただし、盤面外にはみ出した部分は無視する。 - 横方向の壁の場合、始点 (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 回の反復をやり直す。
ツール(入力ジェネレータ・ビジュアライザ)
- Web版: ローカル版より高性能でアニメーション表示が可能です。
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。
入力例 1
30 10 10 13 25 7 14 17 22 0 18 29 1 3 25 14 22 14 29 26 2 3 10 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000000000000000001000000 00000000000000000000001000000 00000000000000000000001000000 00000000000000000000001000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 011111111111111111100000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 111111111110000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000
出力例 1
L L L R U R S D L S R L L L D D L R D D D S R D D S U D U R L U S R D L S U L R L U U L L U D U D L L S U U S D L D U U D D D D U D S D U S U S U D S U L S D L D R R R L L L S L S L R S U S R D D R L 6 1 0 2 3 3 0 0 2 0 7 7 0 7 4 7 8 2 2 0
Story
CEO Takahashi of AtCoder Inc. has introduced several state-of-the-art waxing robots to improve the office environment. He was relieved, thinking that the office floor would soon be sparkling clean, but a serious problem was quickly discovered. Only one controller required to operate the robots had been ordered.
Normally, this would be a hopeless situation, but fortunately, the controller is equipped with an advanced "key configuration" feature. It is a high-performance device that allows individual actions to be assigned to each button for each robot.
Takahashi has entrusted you with solving this difficult problem. Using the limited resources available, he wants you to efficiently wax the entire office floor.
Problem Statement
There is an N \times N grid representing an office. The coordinate of the top-left cell is (0, 0), and the coordinate of the cell i rows down and j columns to the right is (i, j). The perimeter of the N \times N grid is surrounded by walls, and there may also be walls between adjacent cells.
You are to use M robots to wax all cells. The initial position of the k-th robot is (i_k, j_k), and including its initial position, any cell that a robot visits is considered waxed.
All robots are operated simultaneously using a single controller. This controller has K buttons, and before starting the waxing operation, you can configure each button-robot pair to perform one of the five possible actions: move to one of the four adjacent cells (up, down, left, or right), or stay in place. When a button is pressed, all robots simultaneously execute their respective assigned actions for that button. Button assignments can differ between robots. For example, it is possible to configure the controller such that "on button 0, robot 0 moves up while robot 1 moves down." Once waxing begins, the button assignments cannot be changed.
If a robot attempts to move but there is a wall between its current cell and the destination cell, it remains in place. Robots do not interfere with each other, and multiple robots can occupy the same cell.
You may perform at most 2N^2 operations. Design the button assignments and the sequence of operations so that all cells are waxed using as few operations as possible.
Scoring
Let T (T \leq 2N^2) be the length of the output operation sequence, and let R be the number of unwaxed cells. Your score is calculated as follows.
- If R = 0, 3N^2 - T
- If R > 0, N^2 - R
There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.
Input
Input is given from Standard Input in the following format.
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}
- In all test cases, N=30, M=10, and K=10.
- (i_k, j_k) represents the initial position of the k-th robot, and all initial positions are distinct.
- Each line v_{i,0} \cdots v_{i,N-2} is a binary string of length N-1. The j-th character v_{i,j} indicates whether there is a wall (
1) or not (0) between cell (i, j) and cell (i, j+1). - Each line h_{i,0} \cdots h_{i,N-1} is a binary string of length N. The j-th character h_{i,j} indicates whether there is a wall (
1) or not (0) between cell (i, j) and cell (i+1, j). - It is guaranteed that all cells are mutually reachable.
Output
First, output the button assignments in the following format to Standard Output.
c_{0,0} \cdots c_{0,M-1}
\vdots
c_{K-1,0} \cdots c_{K-1,M-1}
Here, c_{i,j} is a single character representing the action taken by the j-th robot when button i is pressed. It must be one of the following 5 types:
U: move one cell upD: move one cell downL: move one cell leftR: move one cell rightS: stay in place
After that, output the operation sequence in the following format.
a_0
\vdots
a_{T-1}
Here, a_t is an integer between 0 and K-1, representing the button pressed on turn t.
Input Generation
Let \mathrm{rand}(L, U) be a function that generates a uniformly random integer between L and U, inclusive.
The initial positions of the M robots are determined by uniformly selecting M distinct coordinates from the N^2 possible cells.
Walls are generated by repeating the following procedure 5 times.
- Randomly choose the direction of the wall from up, down, left, or right.
- Determine the wall length L = \mathrm{rand}(10, 20).
- For vertical walls, choose the starting point (i, j) by i = \mathrm{rand}(5, N-5),\ j = \mathrm{rand}(4, N-6).
If the chosen j is within an absolute distance of 4 from any j used in previously generated vertical walls, redo the direction selection.
For upward walls, set v_{i-L+1, j}, \cdots, v_{i, j} to1. For downward walls, set v_{i, j}, \cdots, v_{i+L-1, j} to1. Ignore any part that goes out of bounds. - For horizontal walls, choose the starting point (i, j) by i = \mathrm{rand}(4, N-6),\ j = \mathrm{rand}(5, N-5).
If the chosen i is within an absolute distance of 4 from any i used in previously generated horizontal walls, redo the direction selection.
For leftward walls, set h_{i, j-L+1}, \cdots, h_{i, j} to1. For rightward walls, set h_{i, j}, \cdots, h_{i, j+L-1} to1. Ignore any part that goes out of bounds. - After generating the wall, check whether all cells are still mutually reachable. If not, reset the wall and restart the 5 iterations.
Tools (Input generator and visualizer)
- Web version: This is more powerful than the local version providing animations.
- Local version: You need a compilation environment of Rust language.
- Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.
Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.
Sample Input 1
30 10 10 13 25 7 14 17 22 0 18 29 1 3 25 14 22 14 29 26 2 3 10 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000010000000000001000000 00000000000000000000001000000 00000000000000000000001000000 00000000000000000000001000000 00000000000000000000001000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000000000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 00000000000000010000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 011111111111111111100000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 111111111110000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000
Sample Output 1
L L L R U R S D L S R L L L D D L R D D D S R D D S U D U R L U S R D L S U L R L U U L L U D U D L L S U U S D L D U U D D D D U D S D U S U S U D S U L S D L D R R R L L L S L S L R S U S R D D R L 6 1 0 2 3 3 0 0 2 0 7 7 0 7 4 7 8 2 2 0