Description

        https://vijos.org/p/1029

现在假设九位勇士已编好了号（感觉好像有人盯着我……）并站好了位置，例如： 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。

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

8
0
5

Hint

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

Source

未分类