九宫重排 ### 题目描述 如下图的九宫格中，放着 1 ~ 8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。 经过若干次移动，可以形成图 2 所示的局面。  我们把上图的局面记为：12345678. 把下图的局面记为：123.46758  显然是按从上到下，从左到右的顺序记录数字，空格记为句点。 题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出 -1。 ### 输入描述 输入第一行包含九宫的初态，第二行包含九宫的终态。 ### 输出描述 输出最少的步数，如果不存在方案，则输出 -1。 ### 输入输出样例 #### 示例 > 输入 ```txt 12345678. 123.46758 ``` > 输出 ```txt 3 ```