晴天小猪历险记之Number

晴天小猪历险记之Number

测试数据来自 system/1029

背景

话说上一回,晴天小猪不畏千难万险、千辛万苦、千磨万难……终于爬上了那座深山,来到了那位隐者的小屋中,但它不知道,有一个问题正等待着它……
晴天小猪一推开门,就发现那里……空无一人?但在屋中央有一个石桌,上面有一些字(强吧),最大的几个:如要见我,先过了这道关再说!
晴天小猪定睛一看,终于发现桌上密密麻麻布满了字,费了九天二猪之力,终于将题目看完,大意是:为了维护世界的和平……我们需要让九位勇士组成一个3*3的阵型去屠龙,但是这个阵型的要求很奇特,要九个人按照强弱依次编号1~9,且阵型中每行、每列、每条长对角线上的数字和都为15,这样才能使龙对勇士和阵型收到的损害最小,但九位勇士光是争夺名次就开始翻脸,各位**(任君想象)忙得不可开交,但晴天小猪也急得不可开交(-_-|||),只好向你求助。

描述

现在假设九位勇士已编好了号(感觉好像有人盯着我……)并站好了位置,例如:
7 8 9
1 2 3
4 5 6
每一次交换都可以将相邻的两位勇士(也就是编号……)交换位置,例如:
7 9 8
1 2 3 (8与9交换)
4 5 6

7 8 9
4 2 3 (4与1交换)
1 5 6
但不能
7 8 9
5 2 3 (1与5交换)
4 1 6
求最少的交换次数,使得九位勇士能在最短的时间内(当然是他们争完后……)以最安全的阵型去屠龙。

P.S:由于不能预测未来,各位设想了许多的阵型(-_-||),所以给了你10组阵型(测试点),每组50个……

格式

输入格式

输入数据一共3*50行,每个数据中用3*3的9个不同的1~9的数字表示初始状态。

(样例就只给几个阵型了^_^)

输出格式

每行一个数,即对应的初始阵型到所需阵型所需最少的交换次数,如果无解,输出-1。

样例1

样例输入1

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

样例输出1

8
0
5

限制

各个测试点5s

提示

欲知后事如何,请做出此题^_^。

来源

Sunnypig

信息

ID
1039
难度
9
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
2
已通过
1
通过率
50%
上传者