引言
AC这道八数码问题，你和楼教主就是兄弟了。。。
题目描述
在一个3*3的九宫格棋盘里，放有8个数码，数码的数字分别是1~8。棋盘中还有一个位置是空着的，用0表示。可以通过在九宫格里平移数码来改变状态(即空格位在九宫格内能上下左右移动)。数码在任何情况下都不能离开棋盘。给出8个数码的初始状态（没放数码的空格用0表示）和目标状态，问从初始状态到目标状态，最少需要经过多少次移动操作。 例如 初始状态为：
目标状态为：
输入格式
两行 第一行9个数字，用空格隔开，表示初始状态 第二行9个数字，用空格隔开，表示目标状态
输出格式
一个数，即最短路径，如果没有答案，则输出-1
样例
样例输入
2 6 4 1 3 7 0 5 8 8 1 5 7 3 6 4 0 2
讯享网样例输出
讯享网31
双向BFS求解
（直接讲解有点难，看一下思路，直接看代码吧，代码详解）
看到这道百度之星的难题，内心不知所措，只知道这个要搜索，而且知道DFS一直搜下去必定超时，所以选用BFS，而BFS也会超，就用双向BFS优化，而且我们知道他的起始状态和最终状态。
首先定义一个 map 判定当前状态是否被访问，分为正向搜索（从初始开始）和反向搜索（从最终开始），每次执行一个换位操作，然后判定是否访问，如果没有，则标记为已访问，再看另一向的搜索是否访问过这个状态，如果访问过则找到答案，输出解即可。
在换位操作时，要判定换位后是否在同一行或同一列
if( nstep >= 0 && nstep <= 8 && ( nstep/3==step/3 || nstep%3==step%3 ) ) //判定是否越界或换后是否在同一行列 如果1~9的全排列，最大的数是，如果我们用一个数组vis[]去记录这个数出现过没有，那该数组最少需要开vis[]，空间复杂度相当大！由于全排列中每一个数不重复，所以我们可以把每一个数对应一个映射(即离散化)，如最小，它的映射就是1，这样我们发现，离散化后，数字的数量变为了全排列的个数(即9!，)。那么我们的vis数组就从亿级变为了十万级，空间复杂度大大缩减&
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/22531.html