491. 八数码
时间限制：1000 MS 内存限制：64 MB
题目描述
# 八数码 ## 题目描述 在一个 $3\times 3$ 的网格中，数字 $1$ 至 $8$ 和一个符号 `x` 各出现一次。其中，`x` 表示空位。 每次操作可以将 `x` 与其上、下、左、右四个方向之一的相邻数字交换，前提是该方向上存在相邻格子。 目标是通过若干次交换，使网格变为如下正确排列： ``` 1 2 3 4 5 6 7 8 x ``` 例如，对于以下初始网格： ``` 1 2 3 x 4 6 7 5 8 ``` 可以让 `x` 依次与右方、下方、右方的数字交换，经过 $3$ 次操作得到正确排列。交换过程如下： ``` 1 2 3 1 2 3 1 2 3 1 2 3 x 4 6 4 x 6 4 5 6 4 5 6 7 5 8 7 5 8 7 x 8 7 8 x ``` 给定一个初始网格，请求出将其变为正确排列所需的最少交换次数。如果无法得到正确排列，则输出 $-1$。 ## 输入格式 从文件 `puzzle.in` 中读入数据。 输入共一行，包含 $9$ 个以空白分隔的符号，按从上到下、每行从左到右的顺序给出初始网格。 例如，题目描述中的初始网格对应的输入为： ``` 1 2 3 x 4 6 7 5 8 ``` ## 输出格式 输出到文件 `puzzle.out` 中。 输出一行一个整数，表示得到正确排列所需的最少交换次数。如果不存在解决方案，则输出 $-1$。 ## 数据范围 - 网格大小固定为 $3\times 3$。 - 输入中数字 $1$ 至 $8$ 和符号 `x` 各出现一次。 - 每次操作只能将 `x` 与存在的上、下、左、右相邻数字交换。 时间限制：$1000$ 毫秒。 内存限制：$64$ MB。 ## 样例输入 ``` 2 3 4 1 5 x 7 6 8 ``` ## 样例输出 ``` 19 ```