[SNOI2019] 积木
题目描述
有一块 $n$ 行 $m$ 列的网格板, $n,m$ 都是奇数。网格上平铺着一些 $1\times 2$ 的积木。积木可以旋转,不能重叠。这些积木共有 $\frac{nm-1}{2}$ 块,也就是说,网格板上只有一格的空位。
你可以做两种操作:
1. 将一块与空白格相邻(指有公共边)的积木旋转 $90^\circ$ 到空白格中;
2. 将一块与空白格积木相邻的积木平移至空白格中。
如图所示(被移动的积木颜色较浅):
![](https://cdn.luogu.com.cn/upload/pic/58669.png)
请你用以上两种操作将给定的网格板变换为指定的状态。
输入输出格式
输入格式
第一行两个正奇数 $n,m$ ,分别表示网格的行数和列数。
接下来 $n$ 行,每行 $m$ 个字符,描述网格板的初始状态:
- `<`表示这个格子是一块积木的左半部分;
- `>`表示这个格子是一块积木的右半部分;
- `n`表示这个格子是一块积木的上半部分;
- `u`表示这个格子是一块积木的下半部分;
- `o`表示这个格子是空的。
接下来另外 $n$ 行,每行 $m$ 个字符,描述你需要将网格板变成的目标状态,格式同上。
输出格式
你需要输出一个字符串,按顺序表示你的操作:
- `L`表示你移动了空白格左侧的积木;
- `R`表示你移动了空白格右侧的积木;
- `U`表示你移动了空白格上方的积木;
- `D`表示你移动了空白格下方的积木。
当然,没有操作的话输出空串就好了。
输入输出样例
输入样例 #1
3 3
nnn
uuu
o<>
<>n
<>u
<>o
输出样例 #1
URLR
输入样例 #2
5 5
n<><>
un<>n
nuonu
u<>un
<><>u
<><>o
<><>n
<><>u
<><>n
<><>u
输出样例 #2
RLLRLRR
说明
#### 数据范围与说明
你输出的操作序列长度不能超过 $8\times 10^6$ 。
对于所有数据, $1\leq n,m\leq 2000$ 。
- 对于 $10\%$ 的数据, $n,m\leq 3$ ;
- 对于另外 $10\%$ 的数据, $n,m\leq 5$ ;
- 对于另外 $20\%$ 的数据, $m=3$ ;
- 对于另外 $20\%$ 的数据, $n,m\leq 50$ ;
- 对于另外 $20\%$ 的数据, $n,m\leq 200$ ;
- 对于余下 $20\%$ 的数据,无特殊限制。
#### SPJ 说明
参考 https://www.luogu.org/discuss/show/114298 ,感谢 @M_sea 的贡献。