#创作计划#广度优先搜索（BFS最基础）

C++的狗

2026-05-02 12:27:38

发布于：浙江

33阅读

0回复

0点赞

注：本人语文不好，所以语句可能会不通顺。我本次是给新手为BFS打上基础的，并没有拓展，谢谢
本次肝了大概4小时左右，且分了3次写

众所周知，发一篇帖子需要头图

这里是我们毕业群里的图片

我们先用一道题作为本次文章的引导
A83422.幅優先探索
这道题的答案是这样的：

#include<iostream>
#include<queue>
using namespace std;
int n,m,sx,sy,gx,gy;
char a[55][55];
bool vis[55][55];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
struct node{
    int x,y,step;
};
void BFS(){
    queue<node> q;
    q.push({sx,sy,0});
    vis[sx][sy]=true;
    while(q.size()){
        node now=q.front();
        q.pop();
        if(now.x==gx&&now.y==gy){
            cout<<now.step;
            return;
        }
        for(int i=0;i<4;i++){
            int nx=now.x+dx[i],ny=now.y+dy[i];
            if(nx<0||nx>n+1||ny<0||ny>m+1){
                continue;
            }
            if(vis[nx][ny]||a[nx][ny]=='#'){
                continue;
            }
            vis[nx][ny]=true;
            q.push({nx,ny,now.step+1});
        }
    }
}
signed main(){
    cin>>n>>m>>sx>>sy>>gx>>gy;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    BFS();
    return 0;
}

没错，这就是广度优先搜索（BFS）

什么是广度优先搜索（BFS）

首先，我们认识一下BFS是什么
这个算法是从起点到终点的最短距离

E.g

⏰不好不好，上学要迟到了！现在即将要到校的你，也即将要迟到，刚好，你有一块可以查看在现在的位置上于学校所有（不包括特别长）路径，手表上显示了：

F # # #
. . . .
. # # .
S . . .

S表示start，意思是开始
F表示finish，表示结束
.表示可行走路径
#表示不可行走路径

“想啥了？当然一直往前跑啊！”
没错，假若你选另一条到的话，那么你一定到学校后被狠狠骂一顿，然后罚站【doge】
当然，如果你仔细看（？），你会发现刚才说的一直往前跑的那条路就是最短的那条路，既省时，又省力

好了，我们回归主题，接下来，我们将拆解这道题目的答案，然后一一讲一下

START😂

首先我们来看这段代码：

int n,m,sx,sy,gx,gy;
char a[55][55];
bool vis[55][55];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

这里的n m分别指这个迷宫的长和宽，而sx sy是指起始位置，而这里的gx gy是终点位置
char a[55][55];是指这个迷宫的"地图"
最后一行int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};,这一行现在看起来好像不知道是什么作用，不过先让子弹飞一会儿，我们接下来看后面一段：

struct node{
    int x,y,step;
};

这里用了struct类型结构，为了方便表示位置和步数，直接用node里的坐标和步数就行了
再看下一段：

queue<node> q;
q.push({sx,sy,0});
vis[sx][sy]=true;

我们先创造一个队列q,类型node
再接着，我们把起始位置和起始步数加入队列，接着把没有走过的路径把它标称走过的路径

再来看个大部分

while(q.size()){
        node now=q.front();
        q.pop();
        if(now.x==gx&&now.y==gy){
            cout<<now.step;
            return;
        }
        for(int i=0;i<4;i++){
            int nx=now.x+dx[i],ny=now.y+dy[i];
            if(nx<0||nx>n+1||ny<0||ny>m+1){
                continue;
            }
            if(vis[nx][ny]||a[nx][ny]=='#'){
                continue;
            }
            vis[nx][ny]=true;
            q.push({nx,ny,now.step+1});
        }
    }

好的，现在我们需要图讲述这大块的代码了
我们再拆几部分

Part 1

 node now=q.front();
 q.pop();

我们现在看这张图：

为了表示方便，我们将横轴为 $x$ ,数轴为 $y$ ,位置表示 $(x,y)$
所有的墙，都表示为#（图中和文字表示）

我们假设 $(7,1)$ 是起点， $(7,3)$ 是终点
以之前的

queue<node> q;
q.push({sx,sy,0});
vis[sx][sy]=true;

现在， $q$ 里的队列是：

[{7,1,0}]

再回来看，现在now的值是

{7,1,0}//此处可能不规范

到第二行后， $q$ 为空队列

Part 2

if(now.x==gx&&now.y==gy){
    cout<<now.step;
    return;
}

这个判断条件是指我们是否在终点,如果是，输出最短步数，退出此函数^[1]

因为在条件语句里的意思是：

在now点的x等同于终点的x，now点的y等同于终点的y

Part 3

 for(int i=0;i<4;i++){
      int nx=now.x+dx[i],ny=now.y+dy[i];
      if(nx<0||nx>n+1||ny<0||ny>m+1){
           continue;
      }
      if(vis[nx][ny]||a[nx][ny]=='#'){
           continue;
      }
      vis[nx][ny]=true;
      q.push({nx,ny,now.step+1})
}

这里是对于后面走的路线的情况
之前我说的先让子弹飞一会儿就在这里"停止"了
这里是探查下一步路径的作用
现在，我们再次回到之前的代码块

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

dx管理的是左右探查路径
而dy则是上下探查路径
例如，我们还是以之前的图片的位置 $(7,1)$

现在在探查下一步左右路径（如图），但这个时候有人会说：

探查右的话这里就出地图边界了

没错，所以再看这一块

 if(nx<0||nx>n+1||ny<0||ny>m+1){
     continue;
 }

这里的nx<0指的是出地图左边界，而nx>n+1是出地图右边界
ny<0是指出地图上边界，ny>m+1是指出地图下边界
现在，我们将这些情况合并起来，就是这里万万不可出现的情况
所以，这里使用continue是为了防止继续执行下去，否则要丸辣

现在大家看到这里小部分可能一脸疑惑❓

如果边界出了，有什么严重？

以后nx和ny会被当下标使用，而后面可能会RE(runtime error，指运行时错误，与编译错误（CE)不同）

Part 4

if(vis[nx][ny]||a[nx][ny]=='#'){
    continue;
}

这里是一个路径判断，指的是

是否有墙？是走过的路径吗？

因为墙视为不可行走路，而走走过路径的话那将可能是到处乱逛,所以也是排除在外的情况

Part 5

vis[nx][ny]=true;
q.push({nx,ny,now.step+1})

成功后，这里将为路过路径，且进入q队列

运行

以本张图片为例

假设起点为 $(7,1)$ ,终点为{7,3)
接着探查路径，发现

只有一个方向可走，这时候，q队列为

[{6,1,1}]

再次继续探查，发现

有两条路径可走，这时候，q队列为

[{6,2,2}{5,1,2}]

以此类推，直到

后结束，
最后最短步数为4
我们再来看一道题：
A8046.仙岛求药

虽然在起点和终点进行了一些标志，让自己去找起点和终点，不过还是套模板就行了

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int N,M,sx,sy,fx,fy;
char a[2005][2005];
bool vis[2005][2005];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct node{
    int x,y,step;
};
int BFS(){
    queue<node> q;
    q.push({sx,sy,0});
    vis[sx][sy]=true;
    while(q.size()){
        node now=q.front();
        q.pop();
        if(now.x==fx&&now.y==fy){
            return now.step;
        }
        for(int i=0;i<4;i++){
            int nx=now.x+dx[i];
            int ny=now.y+dy[i];
            if(nx<1||nx>2000||ny<1||ny>2000){
                continue;
            }
            if(!vis[nx][ny]&&a[nx][ny]!='#'){
                vis[nx][ny]=true;
                q.push({nx,ny,now.step+1});
            }
        }
    }
    return -1;
}
int main(){
    cin>>M>>N;
    for(int i=1;i<=M;i++){
        for(int j=1;j<=N;j++){
            cin>>a[i][j];
            if(a[i][j]=='@'){
                sx=i;
                sy=j;
            }
            if(a[i][j]=='*'){
                fx=i;
                fy=j;
            }
        }
    }
    memset(vis,false,sizeof(vis));
    int result=BFS();
    cout<<result;
}

thanks

我在次必须要谢谢Deepseek人工智能AI,我为了这篇文章，问了他很多问题，他每次都会耐心的回复我，曾经我自学BFS的时候我就是投一个题目，跟他慢慢去解析，我因此也会了最基础的BFS，后面，我也产生了许多问题，后面，我也慢慢理解了
我们因此要怀着不懂就问的心态，去做很多事情
在此，向 $\color{blue}{Deepseek}$ 致谢

代码在函数BFS(void类型)里 ↩︎

有帮助，赞一个

去预览

0/2000

全部评论 2

Eucatastrophe‌
比某些用 AI 死不承认的人好

6天前来自浙江
1
- Eucatastrophe‌
  回复
  Xylophone
  不用，直接写一句“禁言满十四天”就行
  
  6天前来自浙江
  0
Eucatastrophe‌
广搜似乎有很多人写过了，如果你要写创作计划的话不建议。但是如果你只是单纯想写个帖子那是行的

1周前来自浙江
0
- C++的狗
  回复
  Eucatastrophe‌
  饿啊
  
  1周前来自上海
  0
- C++的狗
  回复
  Eucatastrophe‌
  我本来就想写创作计划的
  
  1周前来自上海
  0
- C++的狗
  回复
  Eucatastrophe‌
  我现在在写这篇文章
  
  1周前来自上海
  0