AT_ahc052_a [AHC052A] Single Controller Multiple Robots

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.

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.

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.

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 up - `D`: move one cell down - `L`: move one cell left - `R`: move one cell right - `S`: 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 $ . [Show example](https://img.atcoder.jp/ahc052/ZN1uhrbm.html?lang=en&seed=0&output=sample)

### 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 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. 1. Randomly choose the direction of the wall from up, down, left, or right. 2. Determine the wall length $ L = \mathrm{rand}(10, 20) $ . 3. 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} $ to `1`. For downward walls, set $ v_{i, j}, \cdots, v_{i+L-1, j} $ to `1`. Ignore any part that goes out of bounds. 4. 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} $ to `1`. For rightward walls, set $ h_{i, j}, \cdots, h_{i, j+L-1} $ to `1`. Ignore any part that goes out of bounds. 5. 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](https://img.atcoder.jp/ahc052/ZN1uhrbm.html?lang=en): This is more powerful than the local version providing animations. - [Local version](https://img.atcoder.jp/ahc052/ZN1uhrbm.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc052/ZN1uhrbm_windows.zip): 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.