N*M-1数码

Time Limit: 3000 ms

Memory Limit: 65536 KB

Description

大家都做过8数码和15数码问题吧,今天咱们来个更加高端点的,N*M-1数码。
首先介绍数码移动规则,我们记录X表示空位,其余由1~M*N-1这些不同的数字表示序号,现在给你一个乱序的数码排列,你要移动到一个从上到下、自左向右的一个从小到大的数码排列,并且X最终在右下角。
你有以下的移动方式,我们以一个简单的八数码为例。
1 2 3 1 2 3 4 X 5 --> 4 5 X 记为R(Right, 向右) 7 8 6 7 8 6 1 2 3 1 2 3 4 X 5 --> X 4 5 记为L(Left, 向左) 7 8 6 7 8 6 1 2 3 1 X 3 4 X 5 --> 4 2 5 记为U(Up, 向上) 7 8 6 7 8 6 1 2 3 1 2 3 4 X 5 --> 4 8 5 记为D(Down, 向下) 7 8 6 7 X 6 对于上面的情况,需要经过操作“RD”,就到达了我们需要的状态。

Input

第一行一个数字T(T <= 2014),表示有T组测试数据。 每组测试数据,输入两个整数n和m(1 <= n, m <= 10),表示有n行m列 下面n行,每行m个数字,分别是1~n*m-1的一种排列,并且,0表示空位。

Output

每组测试数据,第一行输出一个整数,表示转移步数(不超过30000步)。 第二行输出一个只包含“L, R, U, D”的字符串。 数据保证所有的情况都有解,如果一步都不用转移,请输出一个0和一个空行,请不要输出多余的字符和空行。

Sample Input

3
3 4
1 2 3 4
5 6 7 8
0 9 10 11
1 1
0
4 3
1 2 3
4 5 6
7 0 9
10 8 11

Sample Output

3
RRR
0

2
DR

Hint

Source

“掌赢杯”南京理工大学第六届程序设计大赛

提交代码