“n的平方减一”谜问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

重排九宫是一个古老的单人智力游戏。据说重排九宫起源于我国古时由三国演义故事“关羽义释曹操”而设计的智力玩具“华容道”,后来流传到欧洲,将人物变成数字。原始的重排九宫问题是这样的:将数字1~8 按照任意次序排在3×3 的方格阵列中,留下一个空格。与空格相邻的数字,允许从上,下,左,右方向移动到空格中。游戏的最终目标是通过合法移动,将数字1~8 按行排好序。在一般情况下,n2-1 谜问题是将数字1~n2-1 按照任意次序排在n×n的方格阵列,留下一个空格。允许与空格相邻的数字从上,下,左,右4 个方向移动到空格中。游戏的最终目标是通过合法移动,将初始状态变换到目标状态。n2-1谜问题的目标状态是将数字1~n2-1 按从小到大的次序排列,最后一个位置为空格。

对于给定的n×n方格阵列中数字1~n2-1初始排列,计算将初始排列通过合法移动变换为目标状态最少移动次数。

Input

输入数据的第1行有1 个正整数n。接下来有2×n行。前n行是n×n方格阵列的中数字1~n2-1的初始排列,每行有n个数字表示该行方格中的数字,0 表示空格。后n行表示n×n方格阵列的中数字1~n2-1的目标状态,每行有n个数字表示该行方格中的数字,0 表示空格。

Output

将计算出的最少移动次数和相应的移动序列输出。第1 行一个整数,表示最少移动次数。
从第2 行开始,依次输出移动序列,用空格的移动方向表示移动序列,用大写字母D、U、L和R分别表示空格向下、上、左和右移动,每行最多输出20个动作。
如果从初始序列无法移动到目标状态,输出:No Solution! 。

Sample Input

3
1 2 3
4 0 6
7 5 8
1 2 3
4 5 6
7 8 0

Sample Output

2
DR

Hint

 

Source