若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1795: 重排n2宫问题

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,315

题目描述

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

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

输入

输入数据的第1行有1 个正整数n(n≤15)。以下的n行是n×n方格阵列的中数字1~n2-1的初始排列,每行有n个数字表示该行方格中的数字, 0 表示空格。

接着的n行是方格阵列中数字1~n2-1的目标状态。

输出

将计算出的最少移动次数和相应的移动序列输出。第1 行是最少移动次数。从第2 行开始,依次输出移动序列。用大写英文字母D,U,L,R 分别表示向下,向上,向左,向右移动,每行输出20个动作。问题无解时输出“No Solution!”

样例输入

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

样例输出

2
DR

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

电子邮件地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Skip Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist