题目描述
重排九宫是一个古老的单人智力游戏。据说重排九宫起源于我国古时由三国演义故事“关羽义释曹操”而设计的智力玩具“华容道”，后来流传到欧洲，将人物变成数字。原始的重排九宫问题是这样的：将数字1～8按照任意次序排在3×3 的方格阵列中，留下一个空格。与空格相邻的数字，允许从上，下，左，右方向移动到空格中。游戏的最终目标是通过合法移动，将数字1～8 按行排好序。最长距离问题考察的是，从数字1～8 在3×3的方格阵列的初始排列A出发，找出与其相应的最长距离目标状态B。换句话说，从A到B的最优移动序列的长度最长。
对于给定的3×3 方格阵列中数字1～8 初始排列，计算与初始排列相应的最长距离目标状态。
输入
输入数据有3 行，每行有3 个数字表示该行方格中的数字，0 表示空格。
输出
将计算出的最长距离目标状态输出。第1 行有2个正整数x 和y，x 是最长距离的值，y是最长距离目标状态个数。从第2行开始，依次输出最长距离目标状态和
到达该最长距离目标状态的最优移动序列。用大写英文字母D，U，L，R 分别表示向下，向上，向左，向右移动。
样例输入
2 6 4
1 3 7
0 5 8
样例输出
31 2
8 7 1
0 3 5
4 6 2
UURDDLUURRDDLURDLLUURDLURRDDLLU
8 1 5
7 3 6
4 0 2
UURDDRULLURRDLLDRRULULDDRUULDDR
参考代码
暂无
解析
暂无
