P5372 [SNOI2019] Bricks

There is a grid board with $n$ rows and $m$ columns, where both $n$ and $m$ are odd. Some $1\times 2$ bricks are tiled on the grid. Bricks can be rotated and cannot overlap. There are $\frac{nm-1}{2}$ bricks in total, which means there is exactly one empty cell on the board. You can perform two kinds of operations: 1. Rotate a brick that is adjacent to the empty cell (sharing a common edge) by $90^\circ$ into the empty cell. 2. Translate a brick that is adjacent to the empty cell into the empty cell. As shown in the figure (the moved brick is in a lighter color):  Please use the two operations above to transform the given grid board into the specified target state.

The first line contains two positive odd integers $n,m$, representing the number of rows and columns of the grid. Then follow $n$ lines, each containing $m$ characters, describing the initial state of the grid board: - `` means this cell is the right half of a brick. - `n` means this cell is the upper half of a brick. - `u` means this cell is the lower half of a brick. - `o` means this cell is empty. Then follow another $n$ lines, each containing $m$ characters, describing the target state you need to transform the board into, in the same format as above.

You need to output a string that represents your operations in order: - `L` means you moved the brick on the left side of the empty cell. - `R` means you moved the brick on the right side of the empty cell. - `U` means you moved the brick above the empty cell. - `D` means you moved the brick below the empty cell. Of course, if there are no operations, output an empty string.

#### Constraints and Notes The length of your output operation sequence must not exceed $8\times 10^6$. For all testdata, $1\leq n,m\leq 2000$. - For $10\%$ of the testdata, $n,m\leq 3$. - For another $10\%$ of the testdata, $n,m\leq 5$. - For another $20\%$ of the testdata, $m=3$. - For another $20\%$ of the testdata, $n,m\leq 50$. - For another $20\%$ of the testdata, $n,m\leq 200$. - For the remaining $20\%$ of the testdata, there are no special restrictions. #### SPJ Notes See https://www.luogu.org/discuss/show/114298. Thanks to @M_sea for the contribution. Translated by ChatGPT 5