Dvanashky
The game "Twelves" is similar to the classic game "Fifteen." It features a board with 5 rows and 3 columns, containing twelve tiles numbered from 1 to 12. Two specific cells in the board, the second and fourth in the middle column, have protrusions and cannot hold tiles. This leaves 13 cells available, each capable of holding one tile at most. Consequently, even when all tiles are placed on the board, one cell remains empty. A move in the game involves sliding a tile into an adjacent empty cell. For instance, by moving tile 11 upwards from the position shown in Fig. 2, then moving 10 upwards, and 9 to the left, you achieve the configuration in Fig. 1.
Your task is to find the shortest sequence of moves from a given initial position to reach the configuration shown in Fig. 1.
Input
The input begins with three numbers on the first line, representing the tiles in the first row of the initial position. The second line contains two numbers, indicating the tiles in the second row. The third, fourth, and fifth lines contain three, two, and three numbers respectively, representing the tiles in the corresponding rows. A tile's absence is denoted by the number 0.
Output
The output should start with a single number K, which is the number of moves in the shortest solution, or -1 if no solution exists or if it requires more than 70 moves. If a solution exists within 70 moves, the second line should contain K characters, representing the sequence of moves as follows:
'U' indicates moving the tile above the empty cell.
'D' indicates moving the tile below the empty cell.
'L' indicates moving the tile to the left of the empty cell.
'R' indicates moving the tile to the right of the empty cell.