蓝桥杯：九宫格重排【BFS】【Python】

如下图的九宫格中，放着 1 ~ 8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。 经过若干次移动，可以形成图 2 所示的局面。

我们把上图的局面记为：12345678.
把下图的局面记为：123.46758

显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出 -1。
输入描述
输入第一行包含九宫的初态，第二行包含九宫的终态。
输出描述
输出最少的步数，如果不存在方案，则输出 -1。
输入输出样例
示例

输入

12345678.
123.46758

输出

3

典型的BFS问题，像这一种在一个平面上移动的，要先移动空的格子，这样就可以只移动一个格子就行，如果是移动数字的话就要移动八个数。可以先把一维数转换成为二维数组的下标来进行移动，移动完后再把其转换成一维数组
具体转换公式:
一维转二维 ： x = index // 数组宽度 ， y = inde

蓝桥杯：九宫格重排【BFS】【Python】最先出现在Python成神之路。