AT_ahc059_a [AHC059A] Stack to Match Pairs

There is an $ N\times N $ grid. The top-left cell has coordinates $ (0,0) $ , and the cell reached by moving $ i $ cells down and $ j $ cells to the right from there has coordinates $ (i,j) $ . $ N $ is even, and for each number from $ 0 $ to $ \frac{N^2}{2}-1 $ , there are exactly two cards with that number. Initially, exactly one of these cards is placed on each cell. You start at position $ (0,0) $ with an empty deck and repeat the following operations: 1. Move to a cell adjacent in one of the four directions (up, down, left, or right). You cannot go outside the $ N\times N $ grid. 2. If there is a card at your current position, you may move it to the top of your deck. If the top two cards in the deck then have the same number, those two cards are removed from the deck. 3. If there is no card at your current position, you may place the top card of your deck onto the current cell. You cannot perform this operation if your deck is empty or if there is already a card at the current cell. You may perform up to $ 2N^3 $ operations. Your goal is to remove all cards from both the grid and your deck. Find a sequence of operations that minimizes the number of **moves**. Note that the number of times you perform operations 2 and 3 counts toward the operation limit, but not toward the evaluation score.

Input is given from Standard Input in the following format: > $ N $ $ a_{0,0} $ $ \cdots $ $ a_{0,N-1} $ $ \vdots $ $ a_{N-1,0} $ $ \cdots $ $ a_{N-1,N-1} $ - In all test cases, $ N = 20 $ is fixed. - $ a_{i,j} $ represents the number written on the card initially placed at cell $ (i,j) $ , and is an integer satisfying $ 0 \leq a_{i,j} \leq \frac{N^2}{2} - 1 $ . - Each value of $ a_{i,j} $ appears exactly twice.

Each operation at turn $ t $ is represented by a single character $ c_t $ as follows: 1. For Operation 1 (move), use the direction: Up: `U`, Down: `D`, Left: `L`, Right: `R` 2. For Operation 2 (pick up): `Z` 3. For Operation 3 (place): `X` Let $ T $ be the total number of operations. Output the result to Standard Output in the following format: > $ c_0 $ $ \vdots $ $ c_{T-1} $ [Show example](https://img.atcoder.jp/ahc059/b8ckwh7N.html?lang=en&seed=0&output=sample)

### Scoring Let $ K $ be the number of moves in your output operation sequence, and let $ X $ be the number of cards remaining on the grid and in your deck at the end. Your score is calculated as follows: - If $ X=0 $ , then your score is $ N^2 + 2N^3 - K $ - If $ X>0 $ , then your score is $ N^2 - X $ ### Input Generation The initial placement of cards $ a_{i,j} $ is generated by randomly shuffling all $ N^2 $ cards. ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc059/b8ckwh7N.html?lang=en): This is more powerful than the local version providing animations and manual play. - [Local version](https://img.atcoder.jp/ahc059/b8ckwh7N.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc059/b8ckwh7N_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.