132 - The 14th Zhejiang University Programming Contest - E
Have you heard or played the game 2048? It is a simple and addictive game. The standard 2048 game consists of a grid of 4 rows and 4 columns, with some numbers tiled in the grid. It is a turn-based single player board game. In each turn, the player can use arrow keys to move the tiles slide towards one direction (Up, Down, Left, Right). If two tiles with the same number touch, they will merge into one.
Bob thinks 2048 is too hard for most of people. So he made a easy version called 64. The rules of 64 is very similar to the rules of 2048. The only difference is the game is played on a 3 x 3 board and the player needs to get a tile of 64. Before he publish his own game, he need to check the game difficulty to ensure the game won't be too hard or too boring for most of people. Therefore, he ask you to write a program to find the shortest operation sequence to win the game.
Here is a detailed game mechanics:
There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:The first line contains three integers R1, P, Q (0 <= R1, P, Q <= 1000000). Each of the next 3 lines contains 3 numbers indicates the initial state of the game. The number on the tiles will be one of 2, 4, 8, 16 or 32. Specially, number 0 means there is no tile in this place.
For each test case, output the shortest operation sequence to win the game. The sequence consists of characters of 'U', 'D', 'L', 'R' (stands for Up, Down, Left and Right respectively). Among all possible solutions, you should choose the one with smallest lexicographical order. If the solution does not exist, output "Always lose!" instead.
2 3 7 4 0 2 0 0 0 0 0 0 0 5 9 1 2 4 2 4 8 4 2 4 2
DDDLDDDRDLDLRLDDDUDLDLDRDLDDDRDLRDLL Always lose!