Quiz#4609
Almost everyone knows the children's game "barley-break" (also known as the sliding puzzle or 15-puzzle). In this problem, you are required to find a solution for a specific position of this puzzle.
The game consists of a square field of size N \times N, divided into 1 \times 1 cells. There are tiles in each cell except one. Each tile contains a number from to N^2 - 1. Each number occurs exactly once. On each turn, you may move a tile adjacent to the empty cell into it, making the moved tile's former cell the new empty cell. Tiles cannot leave the field.
To solve the puzzle means to place the tiles in a specific order:
The empty cell must be in the last cell of the last row.
For the classic 15-puzzle, it looks as follows:
Given a current position, find a sequence of moves (not necessarily the shortest, possibly empty) which leads to the solved state. If there is no solution, output that the position is unsolvable.
The first line contains the integer , the size of the field. The next lines each contain integers. The numbers from to N^2-1 represent tiles; represents the empty cell. Every number from to N^2-1 occurs exactly once.
If the initial position is unsolvable, output "No". Otherwise, output "Yes" in the first line, and the corresponding sequence of moves in the second line (without spaces). Moves are encoded as follows:
'L' — move the tile to the left of the empty cell into it;
'R' — move the tile to the right of the empty cell into it;
'U' — move the tile above the empty cell into it;
'D' — move the tile below the empty cell into it.
The number of moves must not exceed . If there are multiple solutions, you may output any of them.
Constraints
2 \leq N \leq 50
0 \leq a_{ij} \leq N^2 - 1
Example 1