算法总结--BFS广搜1

feizhu_QWQ · 2024-07-13 19:50:38 · 算法·理论

嗨嗨嗨，飞竹小课堂第8课开课啦！
相信大家都会DFS吧，一个万能的算法，以不撞南墙不回头而著名，他全名为深度优先搜索，那我们今天来了解以下，他的好盆友--BFS广度优先搜索~

我们先不着急，先来看一张图：	起点


				终点

如果我让你用DFS来求最短的路径，那么你一定是这样的：	起点
1步
2步
3步	4步	5步	6步	终点

起点		障碍
障碍

	障碍	终点

那你就只能这样走了：

起点			障碍
1步	障碍
2步	3步	4步	5步
3步	4步	障碍	6步	终点

这样就会麻烦许多，而且“不撞南墙不回头”的这一思想也给时间复杂度上带来了不少负担（不得不说DFS是万能的）。

如果我们换一种方式呢？我们先把每一个点能到达的点先标记，再逐个寻找，应该会快不少	起点	1步	2步	障碍
1步	障碍	3步	4步	5步
2步	3步	4步	5步	6步
3步	4步	障碍	6步	终点

这样的操作可能会麻烦一些，不过有明显的顺序，脚踏实地，多好！

那么我们就把他叫做--BFS广度优先搜索！
有请小B登场~ ~

我们可以尝试用code来实现这个过程~：
注：此处采用飞竹的码风，可以自行变化

第一步，我们先需要一个vis数组，标记哪些位置有障碍物，不能走。
第二步，我们需要一个结构体，来记录每次行动的x,y以及步数step
第三步，因为广搜的步骤较多，我们需要把这个结构体改为一个队列，手写的和系统的你可以自己选~
如果你是手写的话，那么head,tail就不要忘记啦！

我们可以用一个while来行动，每一次把上一个最先标记的点踢出来，再让他向上下左右扩散，如果扩散到了终点，那么就return答案，注意，要先判断到达的点是否合法哦！
俗话说得好，不走回头路，所以我们要把走过的地方标记一下哦！

那么最终代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool vis[1005][1005];
char a[1005][1005];
struct node
{
    int x,y,step;
}q[1000005];
bool check(int x,int y)
{
    if(x<1||x>n||y<1||y>m||vis[x][y]==true) return false;
    return true;
}
int head=0,tail=1;
int bfs()
{
    head++;
    q[head].x=1;
    q[head].y=1;
    q[head].step=1;
    vis[1][1]=true;
    while(head-tail+1>0)
    {
        int x=q[tail].x;
        int y=q[tail].y;
        int step=q[tail].step;
        tail++;
        if(check(x-1,y)==true)
        {
            head++;
            q[head].x=x-1;
            q[head].y=y;
            q[head].step=step+1;
            vis[x-1][y]=true;
            if(q[head].x==n&&q[head].y==m)
            {
                return step+1;
            }
        }
        if(check(x,y-1)==true)
        {
            head++;
            q[head].x=x;
            q[head].y=y-1;
            q[head].step=step+1;
            vis[x][y-1]=true;
            if(q[head].x==n&&q[head].y==m)
            {
                return step+1;
            }
        }
        if(check(x,y+1)==true)
        {
            head++;
            q[head].x=x;
            q[head].y=y+1;
            q[head].step=step+1;
            vis[x][y+1]=true;
            if(q[head].x==n&&q[head].y==m)
            {
                return step+1;
            }
        }
        if(check(x+1,y)==true)
        {
            head++;
            q[head].x=x+1;
            q[head].y=y;
            q[head].step=step+1;
            vis[x+1][y]=true;
            if(q[head].x==n&&q[head].y==m)
            {
                return step+1;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='#') vis[i][j]=true;
        }
    }
    cout<<bfs(); 
    return 0;
}

有亿点点长，忍受一下~

那么这就是一个简单的模板啦！
有些例题我就先不讲，我们主要了解一下BFS的模板和原理

这节课就先到这里啦！~~

ヾ(￣▽￣)Bye~Bye~