题目描述

uva 10181

十五数码问题是在一个$\red{4\times 4}$的方格棋盘上,将数字$\red{1,2,3..,14,15}$以任意顺序 置入棋盘的各个方格中,空出一格,通过有限次移动,把一个给定的初始状态变成目 标状态,如图所示。移动规则是:每次只能在空格周围的四个数字中任选一个 移入空格。可以证明的是,一共$\red{16!}$的初态中,有一半是不可能移成目标状态的。

输入格式

第一行为一个整数$\red{N}$,表示有$\red{N}$组数据,随后是$\red{N}$组$\red{4\times 4}$的棋盘初始状态描述。

输出格式

若在$\red{50}$步内不能完成,输出“This puzzle is not solvable. ”,否则输出步数如 样例所示。其中$\red{R,L,U}$和$\red{D}$分别代表左,右,上和下。

样例

输入样例

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.