广度优先搜索
这里要介绍的广度优先搜索也是搜索算法的一种，但是这个和刚刚讲到的深度优先搜索有点不一样的地方在于，深度优先搜索是一次走到底，撞了南墙才回头，而广度优先搜索是每次每个方向都走一步，然后保存起来以便之后在此基础上走。
所以这里很必要的是定义一个新的数据结构，通常是pair来存储当前问题空间的状态，然后把每一步的状态存到队列中，每次就按顺序出队即可。
然后我们先上一道关于BFS的移到非常经典的栗子：
代码：
#include<bits/stdc++.h>
using namespace std;
queue<string> q;
unordered_map<string,int> mp;
int fs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int bfs(string start){
q.push(start);
mp[start] = 0;
string end = “12345678x” ;
while(!q.empty()){
string t = q.front();
q.pop();
if(t == end){
return mp[t];
} //边界条件
int dist = mp[t];
int k = t.find(‘x’);
int a = k/3 , b = k%3;
for(int i = 0; i<4;i++){
int aa = a+fs[i][0];
int bb = b+fs[i][1];
if(aa>=0 && aa<3 && bb >=0 && bb<3){
swap(t[k],t[aa*3+bb]);
if(!mp.count(t)){
q.push(t);
mp[t] = dist+1;
}
swap(t[k],t[aa*3+bb]);
}
}
}
return -1;
}
int main()
{
string start;
for(int i = 0;i<9;i++){
char c;
cin>>c;
start += c;
}
cout<<bfs(start)<<‘\n’;
return 0;
}
分析：这里我们就是把初始状态输入进去，然后往每一个可以走的方向都去走向一步，直到发现走到目标位置后退出；
缺点：对于空间的要求比较高，因为往往是成指数函数的趋势存储新的状态，一旦目标节点所在层数过深就会MLE；
优点：时间要求不高，而且可以求出最短路，而DFS只能判断是否存在路！
深搜和广搜的一些共同之处：
基本的DFS和BFS的函数我们都可以写成以下格式：
##############if（边界条件）{
***********return ；******
}
for（循环条件）{
####判断可行性###
####走下一步，使新状态入队####
}
剪枝：
·可行性剪枝，如果搜索到某一个位置的时候我们发现此时已经不满足条件（跑出了地图，消耗的时间已经超过要求……），我们就要及时放弃！
·最优性剪枝：如果搜索到一个位置时，此时我们所观测的那个Key Number已经不如当前存在的最优了，我们也要及时放弃！
