题目描述
The 15-puzzle is a very popular game: you have certainly seen it even if you don't know it by that name. It is constructed with 15 sliding tiles, each with a different number from 1 to 15, with all tiles packed into a 4 by 4 frame with one tile missing. The object of the puzzle is to arrange the tiles so that they are ordered as below: The only legal operation is to exchange the missing tile with one of the 2, 3, or 4 tiles it shares an edge with. Consider the following sequence of moves: A random puzzle position The missing tile moves right (R) The missing tile moves upwards (U) The missing tile moves left (L) We denote moves by the neighbor of the missing tile is swapped with it. Legal values are “R,'' “L,'' “U,'' and “D'' for right, left, up, and down, based on the movements of the hole. Given an initial configuration of a 15-puzzle you must determine a sequence of steps that take you to the final state. Each solvable 15-puzzle input requires at most 45 steps to be solved with our judge solution; you are limited to using at most 50 steps to solve the puzzle.
输入
The first line of the input contains an integer n indicating the number of puzzle set inputs. The next 4n lines contain n puzzles at four lines per puzzle. Zero denotes the missing tile.
输出
For each input set you must produce one line of output. If the given initial configuration is not solvable, print the line “This puzzle is not solvable.'' If the puzzle is solvable, then print the move sequence as described above to solve the puzzle.
样例输入
2
2 3 4 0
1 5 7 8
9 6 10 12
13 14 11 15
13 1 2 4
5 0 3 7
9 6 10 12
15 8 11 14
样例输出
LLLDRDRDR
This puzzle is not solvable.
参考代码
暂无
解析
暂无
