BFS（宽度优先搜索、广度优先搜索）

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止 。

 

BFS算法常用于求最短路径或者求扩散性质的区域问题。

（1）走迷宫最短路径

（2）数字按规则转换的最少次数

（3）棋盘上某个棋子N步后能到达的位置总数

（4）病毒扩散计算

（5）图像中连通块的计算。

模板

可以分为四个步骤：初始化（初始化队列和所求的值） -> 判空取队头（判断是否为空并取出队头） -> 拓展（利用队头去扩展）->依次四个方向 -> 判断入队（如果符合，将该点入队）。

void bfs(){
	queue<int>q;
    //此处定义一个哈希map存距离或者定义全局二维数组存距离
	q.push(初始位置);
    //初始位置距离赋值0
	int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//四个方向上的向量
	
	while(q.size()){
        auto t = q.front();
        q.pop();//取出队头的点，用该点向周围扩散。
		for(int i=0;i<4;i++){
            int a=   ,b=  
            if(check(j)){       //如果该点可行就将它加入队列中
            q.push(j);		
            //实施相应的操作 
            }
        }
	} 
} 

#include<bits/stdc++.h>
using namespace std;
const int N=110;
typedef pair<int ,int> PII;
int n,m;
int g[N][N];//存放地图
int d[N][N];//存放该点到起点的距离
 
int bfs(){
	queue<PII> q;
	memset(d, -1 ,sizeof d);//将值全部初始化为-1 代表还没有走过
	d[0][0]=0;//第一个点已经走过
	q.push({0,0});//将起点插入队列中
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//四个方向上的向量
	while(q.size()){//判断队列是否为空
		auto t=q.front();//取出对头元素
		q.pop();//弹出队头元素
		for(int i=0;i<4;i++){
			int x=t.first+dx[i],y=t.second+dy[i];
			if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1){//x、y符合条件 该位置为0 且没有走过
				d[x][y]=d[t.first][t.second]+1;//离起点距离加 1
				q.push({x,y});//坐标入队
			}
		}
	}
	return d[n-1][m-1];
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		cin>>g[i][j];
	cout<<bfs()<<endl;
	return 0;
}