Preparing NOJ

最长距离问题

1000ms 65536K

Description:

     重排九宫是一个古老的单人智力游戏。据说重排九宫起源于我国古时由三国演义故事“关羽义释曹操”而设计的智力玩具“华容道”,后来流传到欧洲,将人物变成数字。原始的重排九宫问题是这样的:将数字18按照任意次序排在3´3 的方格阵列中,留下一个空格。与空格相邻的数字,允许从上,下,左,右方向移动到空格中。游戏的最终目标是通过合法移动,将数字18 按行排好序。最长距离问题考察的是,从数字18 3´3的方格阵列的初始排列A出发,找出与其相应的最长距离目标状态B。换句话说,从AB的最优移动序列的长度最长。

                                       

   对于给定的3´3 方格阵列中数字18 初始排列,编程计算与初始排列相应的最长距离目标状态。

Input:

  输入数据有3 行,每行有3 个数字表示该行方格中的数字,0 表示空格。

Output:

      将计算出的最长距离目标状态输出。第1 行有2个正整数x yx 是最长距离的值,y是最长距离目标状态个数。从第2行开始,依次输出最长距离目标状态和到达该最长距离目标状态的最优移动序列。用大写英文字母DULR 分别表示向下,向上,向左,向右移动。

Sample Input:

2 6 4
1 3 7
0 5 8

Sample Output:

31 2
8 7 1
0 3 5
4 6 2
UURDDLUURRDDLURDLLUURDLURRDDLLU
8 1 5
7 3 6
4 0 2
UURDDRULLURRDLLDRRULULDDRUULDDR

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1336

Tags

Submitted 4

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet