广度优先(BFS)

先看一道简单的题，迷宫问题：

洛谷P1746 离开中山路：P1746 离开中山路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
#include<cstring>
#include<queue>
#include <utility>
#define N 1002
using namespace std;


char g[N][N];
int dist[N][N];
queue< pair<int,int> > q;
int n,x1,y1,x2,y2;

int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

void bfs(int x,int y)
{
q.push(make_pair(x,y));
dist[x][y]=0;
while(!q.empty())
{
pair<int,int> t = q.front();
q.pop();
for(int i=0;i<4;i++)
{
int a = t.first + dx[i];
int b = t.second + dy[i];

if(a<1 || a>n || b<1 || b>n) continue;
if(g[a][b] != '0') continue;
if(dist[a][b] >=0) continue;

q.push(make_pair(a,b));
dist[a][b] = dist[t.first][t.second] +1;

if(a==x2 && b==y2) return ;
}

}

}

int main()
{
memset(dist,-1,sizeof(dist));
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",g[i] +1);
}
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
bfs(x1,y1);
printf("%d",dist[x2][y2]);

return 0;
}

先看一下遍历顺序：

可以看出BFS和DFS有着很大的区别，并不是“一条路，走到黑”。而是根据举例根节点的具体进行遍历。

假如先确定顺序是从左到右，那么有什么办法可以从左到右进行遍历呢？

很难想？那就别想了，直接上答案：队列。先进先出啊。

是不是很神奇？

原文地址：https://blog.csdn.net/2303_77275067/article/details/139811156

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！