Flipping
本题没有可用的提交语言。
Description
You are given an $n \times m$ ($n, m \leq 400$) cell grid where each cell contains either a $0$ or a $1$. You wish to make all cells contain $0$. Initially you are located in the upper left cell of the grid and in one move you can move into an adjacent cell (one sharing a side with your current cell). When you move into a new cell, its value flips to the opposite ($0$ to $1$ and vice versa).
Find a journey of at most $4\cdot 10^5$ moves after which all grid cells contain a $0$. You can finish in any cell and you can visit each cell any number of times.
The first line contains two integers $n$ and $m$ ($2 \leq n, m \leq 400$), the height and width of the grid. The next $n$ lines each contains a string of $m$ characters (either 0 or 1), the values of the corresponding row.
Output a single string of length at most $4\cdot 10^5$ which describes your journey. The $i$-th character should be one of "U", "R", "D" or "L", meaning that your $i$-th move is to the adjacent cell up, right, down or left, respectively. It is forbidden to go outside of the grid. If there are multiple solutions, output any of those. The output string can be empty.
Input
The first line contains two integers $n$ and $m$ ($2 \leq n, m \leq 400$), the height and width of the grid. The next $n$ lines each contains a string of $m$ characters (either 0 or 1), the values of the corresponding row.
Output
Output a single string of length at most $4\cdot 10^5$ which describes your journey. The $i$-th character should be one of "U", "R", "D" or "L", meaning that your $i$-th move is to the adjacent cell up, right, down or left, respectively. It is forbidden to go outside of the grid. If there are multiple solutions, output any of those. The output string can be empty.
2 3
010
001
RDRL