本文主要是介绍BFS：845. 八数码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
在一个 3×33×3 的网格中，1∼81∼8 这 88 个数字和一个 x 恰好不重不漏地分布在这 3×33×3 的网格中。
例如：
1 2 3
x 4 6
7 5 8
在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3
4 5 6
7 8 x
例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
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
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将 3×33×3 的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出 −1−1。
输入样例：
2 3 4 1 5 x 7 6 8
输出样例
19
| 难度：中等 |
| 时/空限制：1s / 64MB |
| 总通过数：47772 |
| 总尝试数：69209 |
| 来源：模板题,AcWing,Airbnb面试题 |
| 算法标签 |
思路
1.宽度优先搜索：是寻找所有可能的情况，然后找到符合条件的最短路，即可
2.交换两个位置之后需要恢复原来的位置，因为需要交换另外三次（如果可以交换）
3.把一维的坐标转换成二维的坐标，使用这行代码
int x=k/3,y=k%3;4.宽度优先搜索还是使用队列，这道题目多了一个判断，如果字符串和我们设定的字符串相同（12345678x），就输出答案 ，经过若干次操作也不能把字符串处理成我们需要的情况，就在循环外输出-1。
5.代码细节：
（1）万能头文件的使用
#include<bits/stdc++.h>（2）stl的使用
auto t=q.front();if(!d.count(t))（3）四个方向的方向向量：就是0，1，-1，0错开即可，意思就是dx那里是1，dy对应的就是用0，dx那里是0,dy那里就对应使用1，dx是-1，dy就使用0,dx使用0，dy使用-1
（4）输入字符串但是中间有空格，使用字符串输入，使用引用符号，并且使用加号把单个的字符串在一起，存在一个字符串里面
char s[2];string state;for(int i=0;i<9;i++){scanf("%s",s);state+=*s;}代码
#include<bits/stdc++.h>
using namespace std;int bfs(string state)
{queue<string> q;unordered_map<string,int> d;q.push(state);d[state]=0;while(q.size()){auto t=q.front();q.pop();string end="12345678x";if(t==end) return d[t];int distance=d[t];int k=t.find('x');int x=k/3,y=k%3;int dx[4]={0,1,-1,0},dy[4]={1,0,0,-1};for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if(a>=0&&a<3&&b>=0&&b<3){swap(t[a*3+b],t[k]);if(!d.count(t)){d[t]=distance+1;q.push(t);}swap(t[a*3+b],t[k]);}}}return -1;
}int main()
{char s[2];string state;for(int i=0;i<9;i++){scanf("%s",s);state+=*s;}printf("%d\n",bfs(state));return 0;
}
这篇关于BFS：845. 八数码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
