[蓝桥杯][历届试题]九宫重排
Description
如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。
| 1 | 2 | 3 |
|---|---|---|
| 4 | 5 | 6 |
| 7 | 8 |
| 1 | 2 | 3 |
|---|---|---|
| 4 | 6 | |
| 7 | 5 | 8 |
我们把第一个图的局面记为：12345678。把第二个图的局面记为：123.46758。显然是按从上到下，从左到右的顺序记录数字，空格记为句点。本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
Input Format
输入第一行包含九宫的初态，第二行包含九宫的终态。
Output Format
输出最少的步数，如果不存在方案，则输出-1。
12345678.
123.46758
3
Source
蓝桥杯