BFS广度优先搜索(宽搜)
使用场景
只有当边值全为1的时候才可以用BFS求最短路
基本框架
queue<-初试状态
while (queue)
{
t<-队头;
拓展 t;
}
未用STL直接手写queue
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m;
int g[N][N];
int d[N][N];
PII q[N*N];
int bfs()
{
int f=0,r=0;
q[0]={0,0};
memset(d,-1,sizeof(d));
d[0][0]=0;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
while(f<=r)//队空,输出
{
auto t=q[f++];//这里给的是坐标
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)//判断条件
{
d[x][y]=d[t.first][t.second]+1;//距离矩阵更新+1
q[++r]={x,y};//把刚才遍历的那个点加入q队列
}
}
}
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;
}
用STL自带的queue
需要输出路径
加一个记录路径的数组prev
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m;
int g[N][N];
int d[N][N];
PII q[N*N],p[x][y];
int bfs()
{
int f=0,r=0;
q[0]={0,0};
memset(d,-1,sizeof(d));
d[0][0]=0;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
while(f<=r)
{
auto t=q[f++];//这里给的是坐标
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)//判断条件
{
d[x][y]=d[t.first][t.second]+1;//距离矩阵更新+1
p[x][y]=t;
q[++r]={x,y};//把刚才遍历的那个点加入q队列
}
}
}
int x=n-1,y=m-1;
while(x||y)
{
cout<<x<<' '<<y<<endl;
auto t=p[x][y];
x=t.first,y=t.second;//沿着这个路往后走
}
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;
}