«算法设计：
对于给定的 nxn 方格阵列中数字 1～n2-1 初始排列，计算将初始排列通过合法移动变换为目标状态最少移动次数。
1405: 算法实现题 5-26 n*n-1 谜问题
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $0$ | 正确数量 | $0$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | 回溯 |
Description
重排九宫是一个古老的单人智力游戏。据说重排九宫起源于我国古时由三国演义故事“关羽义释曹操”而设计的智力玩具“华容道”，后来流传到欧洲，将人物变成数字。原始的重排九宫问题是这样的：将数字 1～8 按照任意次序排在 3x3 的方格阵列中，留下一个空格。与空格相邻的数字，允许从上，下，左，右方向移动到空格中。游戏的最终目标是通过合法移动，将数字 1～8 按行排好序。在一般情况下，n2-1 谜问题是将数字 1～n2-1 按照任意次序排在 nxn 的方格阵列中，留下一个空格。允许与空格相邻的数字从上，下，左，右 4 个方向移动到空格中。游戏的最终目标是通过合法移动，将初始状态变换到目标状态。n2-1 谜问题的目标状态是将数字 1～n2-1 按从小到大的次序排列，最后一个位置为空格。
«算法设计：
对于给定的 nxn 方格阵列中数字 1～n2-1 初始排列，计算将初始排列通过合法移动变换为目标状态最少移动次数。
«算法设计：
对于给定的 nxn 方格阵列中数字 1～n2-1 初始排列，计算将初始排列通过合法移动变换为目标状态最少移动次数。
Input
输入的第 1 行有 1 个正整数 n。以下的 n 行是 nxn 方格阵列的中数字 1～n2-1 的初始排列，每行有 n 个数字表示该行方格中的数字， 0 表示空格。
Output
将计算出的最少移动次数和相应的移动序列输出。第 1 行是最少移动次数。从第 2 行开始，依次输出移动序列。
Sample Input复制
3
1 2 3
4 0 6
7 5 8
Sample Output复制
2
5 8
推荐代码 查看1405 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$ $ms] | |||
| 内存最少[$ $KB] | |||
| 第一AC | |||
| 第一挑战 |
赛题来源/所属竞赛 NA 算法导论(第三版)中文完整高清版
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|