|
|
|
|
背景 Background |
|
|
|
话说上一回，晴天小猪不畏千难万险、千辛万苦、千磨万难……终于爬上了那座深山，来到了那位隐者的小屋中，但它不知道，有一个问题正等待着它……
晴天小猪一推开门，就发现那里……空无一人？但在屋中央有一个石桌，上面有一些字（强吧），最大的几个：如要见我，先过了这道关再说！
晴天小猪定睛一看，终于发现桌上密密麻麻布满了字，费了九天二猪之力，终于将题目看完，大意是：为了维护世界的和平……我们需要让九位勇士组成一个3*3的阵型去屠龙，但是这个阵型的要求很奇特，要九个人按照强弱依次编号1~9，且阵型中每行、每列、每条长对角线上的数字和都为15，这样才能使龙对勇士和阵型收到的损害最小，但九位勇士光是争夺名次就开始翻脸，各位**（任君想象）忙得不可开交，但晴天小猪也急得不可开交（-_-|||），只好向你求助。
|
|
|
|
|
|
|
|
描述 Description |
|
|
|
现在假设九位勇士已编好了号（感觉好像有人盯着我……）并站好了位置，例如：
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个…… |
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
输入数据一共3*50行，每个数据中用3*3的9个不同的1~9的数字表示初始状态。
（样例就只给几个阵型了^_^）
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
每行一个数，即对应的初始阵型到所需阵型所需最少的交换次数，如果无解，输出-1。 |
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
各个测试点5s |
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1225 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
