#创作计划# BFS广度优先搜索详解
2025-11-24 18:52:33
发布于：四川
PS:已更正bfs代码，感谢 @宋雨琦才是真神 提出的问题。
对于BFS，我来谈一谈自己的理解。首先，我们从一道最基础的题来进行学习:
洛谷B3625 迷宫寻路（仔细阅读哦，我就不解释了）
https://www.luogu.com.cn/problem/B3625#submit
对于这道题以及所有的BFS题目的核心，我们的思想是这样的：
直接暴力枚举每一种情况，并把其放入队列（因为队列符合BFS算法所需要的先进先出），在枚举完这一种情况的所有符合条件的衍生情况并入队后，把这一种情况出队，枚举下一个，也就是出队后的队首元素，直至找到符合条件的答案。又或者是说，枚举完了所有情况，都没有找到正确答案，在程序运行中体现这一点的是队列为空都没有找到答案的情况。
示例：
有一个n*m的方格，里面'#'的地方是不能走的，起点是（1，1)，终点是（n，m），那么如以下图形：
.##.#
.#. . .
. . .#.
刚开始的队列（数据类型可以是pair、结构体等）：
（1，1）
想要从（1，1）走到（n，m），我们可以按刚才说的流程，把（1，1）的所有衍生坐标入队，而且入队条件为该区域不为'#'且在n*m以内。
入队后的队列：
（1，1） （2，1）
为什么只有（2，1）一个呢，这是因为对于（1，1）来说，不考虑入队条件，（1，1）确实有四种衍生情况：（0，1）（2，1）（1，2）（1，0），但其中，（0，1）（1，0）超出了n*m的范围，而（1，2）则是不能通行的'#'区域，所以最终，只有（2，1）一个符合条件的坐标被加入到了队列。可到这就完了吗？不，我们在上面说过，还需要把枚举完了所有情况的（1，1）节点出队，因为它不是答案，且没有了为答案提供价值的能力。这一点在代码里的体现不太一样，在代码中，作者是把（1，1）节点先用t保存起来，再直接出队，之后再用t代替（1，1）的作用,现在，我们就完成了一次程序将要做的枚举。之后再照着这种方式继续即可求解出答案。
全部过程展示（队列，，一行为一次枚举）：
（1，1）
（2，1）
（3，1）
（3，2）
（3，3）
（2，3）
（2，4）
（2，5）
（2，6）
因数据太水一条路拉通
代码实现：
对于程序实现上的补充：
进行一次枚举时，我们需要一个标记来表示这个路段是否走过，否则，我们的程序会在两个路段上反复横跳。
#include<iostream>
#include<queue>
using namespace std;
int n,m;
char map[1001][1001];
int dx[10]={0,0,1,-1},dy[10]={1,-1,0,0};
bool vis[1001][1001];
bool bfs(int map_x,int map_y){
queue<pair<int,int> > q;
q.push({map_x,map_y});
while(!q.empty()){
auto t=q.front();
q.pop();
for(int i=0;i<4;i++){
int tx=t.first+dx[i];
int ty=t.second+dy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&map[tx][ty]!='#'&&!vis[tx][ty]){
if(tx==n&&ty==m){
return true;
}
vis[tx][ty]=1;
q.push({tx,ty});
}
}
}
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>map[i][j];
}
}
bool x=bfs(1,1);
if(x){
cout<<"Yes";
}else{
cout<<"No";
}
return 0;
}
全部评论 17
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
2025-11-21 来自 浙江
0
有帮助，赞一个