Scarral and Puzzle

Scarral and Puzzle

测试数据来自 Scoj/1001

Description

ScarralScarral到达了密室大门,发现大门左侧有一行文字。

想打开大门,请先完成右侧的拼图!拼图中隐含着密码。

ScarralScarral往右一看,果然有个数字拼图。

ScarralScarral转念一想:

这不就是数字华容道吗?!!

拼图是一个 n×nn\times n 的由木块组成的矩阵,木块编号为 11~n21n^2-1 每个木块都只能相邻的空格移动,不能拿起。

经过若干次的移动,可以将拼移动为 11~n21n^2-1 的顺序矩阵。

n=3n=3 时,最后要求移动为

1 2 3
4 5 6
7 8 空

给出华容道的大小 nn 和当前华容道的乱序摆放位置,求还原原序的最小步数。


Input

1111 个正整数 nn,表示有一个 n×nn \times n 的华容道。
接下来键入 nnnn 列的矩阵,表示当前华容道的乱序摆放位置,若某数为 00,则代表该位置暂无滑块。

信息

ID
1003
难度
10
分类
(无)
标签
(无)
递交数
3
已通过
0
通过率
0%
上传者