题目描述
重排九宫是一个古老的单人智力游戏。据说重排九宫起源于我国古时由三国演义故事“关羽义释曹操”而设计的智力玩具“华容道”,后来流传到欧洲,将人物变成数字。原始的重排九宫问题是这样的:将数字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
参考代码
暂无
解析
暂无