BFS 算法模板及使用

ycx20120224 · 2024-10-13 20:23:18 · 算法·理论

BFS 算法模板及使用

什么是 BFS 算法？

BFS （Breadth-First Search） 算法，中文全称广度优先搜索（宽度优先搜索），区别于 DFS 算法一条路走到黑的本质， BFS 使用扩散性搜索。它将会根据规则一层一层向下搜索，容易发现，BFS 算法找到的路径一定是最短的，同时，它的时间复杂度较 DFS 而言短了不少，但代价就是空间复杂度比DFS大很多。

BFS 算法的模板长什么样？

queue<node> q;
void bfs(){
    while(!q.empty())
    {
        node temp=q.front();
        q.pop();
        if(完成目标)
        {
            记录;
            return;
        }
        for(int i=0;i<m;i++)//m为方向数组长度
        {
            int xx=temp.x+dx[i];
            int yy=temp.y+dy[i];
            if(下标越界||已被标记)
            {
                continue;
            }
            mark[xx][yy]=1;
            q.push(node{xx,yy});//注意，node{xx,yy}这种形式只适用于C++20及以上版本
        }
    }
}

BFS 算法适用于哪些问题？

BFS 算法的用途十分地广，可以解决迷宫问题，最短路问题等，以下是一些例题（这只是做例子使用，代码不做过多解释，请勿抄袭！

求细胞数量（P1451）

题目描述

一矩形阵列由数字 0 到 9 组成，数字 1 到 9 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

输入格式

第一行两个整数代表矩阵大小 n 和 m。

接下来 n 行，每行一个长度为 m 的只含字符 0 到 9 的字符串，代表这个 n \times m 的矩阵。

输出格式

一行一个整数代表细胞个数。

样例 #1

样例输入 #1

样例输出 #1

数据规模与约定

对于 100 \% 的数据，保证 1\le n,m\le100。

解法

此题需要每次都把发现的整个细胞做出标记：

#include<bits/stdc++.h>
using namespace std;
struct node{
    long long x,y;
};
long long m,n,sum;
queue<node>q;
string a[105];
int dx[10]={0,0,-1,1,0};
int dy[10]={0,1,0,0,-1};
void bfs(int x,int y)
{
    node te;
    te.x=x,te.y=y;
    q.push(te);
    while(!q.empty())
    {
        node temp=q.front();
        q.pop();
        a[temp.x][temp.y]='0';
        for(int i=1;i<5;i++)
        {
            int xx=temp.x+dx[i];
            int yy=temp.y+dy[i];
            if(xx<1 || xx>n || yy<0 || yy>=m)
            {
                continue;
            }
            if(a[xx][yy]=='0')
            {
                continue;
            }
            node t;
            t.x=xx;
            t.y=yy;
            q.push(t);
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i][j]!='0')
            {
                sum++;
                bfs(i,j);
            }
        }
    }
    cout<<sum;
    return 0;
}

做了一道橙题，做一道黄题试试手吧！

马的遍历（P1443）

题目描述

有一个 n\times m 的棋盘，在某个点 (x, y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 n, m, x, y。

输出格式

一个 n\times m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 -1）。

样例 #1

样例输入 #1

3 3 1 1

样例输出 #1

0    3    2    
3    -1   1    
2    1    4

提示

数据规模与约定

对于全部的测试点，保证 1\le x\le n \le 400，1 \le y\le m\le 400。

解法

#include<iostream>
#include<queue>
using namespace std;
struct node{
    long long x,y;
};
long long n,m,x,y,vis[405][405],mark[405][405],cnt=0;
int dx[10]={2,2,1,1,-1,-1,-2,-2};
int dy[10]={1,-1,2,-2,2,-2,1,-1};
queue<node> q;
void putit()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cout<<mark[i][j]<<" ";
        }
        cout<<endl;
    }
}
void bfs()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            mark[i][j]=-1;
    q.push(node{x,y});
    mark[x][y]=0;
    while(!q.empty())
    {
        node temp=q.front();
        q.pop();
        for(int i=0;i<8;i++)
        {
            long long xx=temp.x+dx[i],yy=temp.y+dy[i];
            if(xx>n || yy>m || xx<1 || yy<1 || mark[xx][yy]!=-1)
            {
                continue;
            }
            q.push(node{xx,yy});
            mark[xx][yy]=mark[temp.x][temp.y]+1;
        }
    }
}
int main(void)
{
    cin>>n>>m>>x>>y;
    bfs();
    putit();
    return 0;
 }

现在，你已经会使用 BFS 算法了，快去题库做题吧！