Twelves#5303
The game "Twelves" is similar to the classic game "Fifteen." It consists of a box of size rows by columns and twelve tiles numbered from to . Two specific cells in the box — the second and fourth in the middle column — have protrusions and cannot hold tiles. Each of the remaining cells can contain at most one tile. Thus, when all tiles are placed in the box, there is still one empty cell. A move in the game consists of sliding a tile into an adjacent empty cell. For example, moving tile upward from the position shown in Fig. 2, then upward, and to the left, gives the position shown in Fig. 1.
Your task is, for a given initial position, to determine the shortest sequence of moves to reach the configuration shown in Fig. 1.
The first line of input contains three numbers — the numbers of the tiles in the first row of the initial position. The second line contains two numbers, indicating the numbers of the tiles in the second row. The third, fourth, and fifth lines contain three, two, and three numbers, respectively, which represent the numbers of the tiles in the corresponding rows. The absence of a tile is indicated by the number .
The first line of output should contain a single number — the number of moves in the shortest solution, or if there is no solution or if it requires more than moves. If there is a solution in not more than moves, the second line should contain characters, which describe the solution as a sequence of moves in the following way:
The character 'U' means the tile located above the empty cell is moved.
The character 'D' means the tile located below the empty cell is moved.
The character 'L' means the tile located to the left of the empty cell is moved.
The character 'R' means the tile located to the right of the empty cell is moved.
Example 1