BFS的基本应用——flood fill && 最短路_bfs应用

bfs的核心就是一层一层往外扩展，在bfs中会用到一个队列，又由于是一层一层往外扩展的，故而可以用来求连通的问题，同时相当于每次往外扩展的边权都是1，所以这个队列是有序的，相当于dijkstra算法中的优先队列，那么也可以用来求边权为1的最短路问题。

Flood Fill

Flood Fill问题实际就是连通块问题，可以求二维图中连通块的数量，连通块的面积，连通块与非连通块之间的关系，连通块的边界、周长等问题。核心就是在在搜到非连通位置时的不同处理。

另外连通分四连通和八连通，四连通可以用向量来解决，而八连通可以直接围绕当前访问的点访问一个3*3的矩形，然后将中间那一块儿扣掉，当然向量也可以。

另外用到的队列既可以用queue，也可以用数组来模拟。

1097. 池塘计数（活动 - AcWing）

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
pii q[1000010];
int hh,tt;
int st[1010][1010];
int n,m;
char s[1010][1010];
void bfs(int a,int b)
{
    st[a][b]=1;
    hh=tt=0;
    q[tt++]={a,b};
    while(hh<tt)
    {
        auto t=q[hh++];
        for(int i=t.x-1;i<=t.x+1;i++)
        {
            for(int j=t.y-1;j<=t.y+1;j++)
            {
                if(i==t.x&&j==t.y) continue;
                if(i<1||i>n||j<1||j>m) continue;
                if(s[i][j]!='W'||st[i][j]) continue;
                q[tt++]={i,j};
                st[i][j]=1;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    int c=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!st[i][j]&&s[i][j]=='W')
            {
                c++;
                bfs(i,j);
            }
        }
    }
    cout<<c;
}

 1098. 城堡问题（活动 - AcWing）

 

思路：这题看上去比较麻烦，因为它不是相邻的格子有阻碍，而是用一个数来表示当前位置四周的情况，而且这里还需要求面积。我们先来看它给定的数1,2,4,8，显然就是二进制数的某一位，那么我们实际上可以直接bfs，用该点上的数来判断将要延伸的位置是否可以达到就好。另外面积也很简单，给bfs加个返回值就好。

 

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
pii q[2500];
int hh,tt;
int n,m;
int st[100][100];
int g[100][100];
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
int bfs(int a,int b)
{
    st[a][b]=1;
    hh=tt=0;
    q[tt++]={a,b};
    int s=0;
    while(hh<tt)
    {
        auto t=q[hh++];
        s++;
        for(int i=0;i<4;i++)//0
        {
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m) continue;
            if(st[nx][ny]) continue;
            if(g[t.x][t.y]>>i&1) continue;//说明有墙
            q[tt++]={nx,ny};
            st[nx][ny]=1;
        }
    }
    return s;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&g[i][j]);
        }
    }
    int mx=0,c=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!st[i][j])
            {
                c++;
                int tmp=bfs(i,j);
                mx=max(mx,tmp);
            }
        }
    }
    cout<<c<<endl<<mx;
}

1106. 山峰和山谷(活动 - AcWing)

思路：这里就涉及到对边界值的处理，我们只需要在访问到边界的时候判断一下非连通块位置的值，与连通块之间的关系即可。因为要记录一下情况，所以我们多传两个参数进函数即可，另外一定要注意，这里需要传地址，不能只传值，只有数组传值可以进行改变。

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
pii q[1000010];
int st[1010][1010];
int g[1010][1010];
int n,hh,tt;
void bfs(int a,int b,int&h,int&v)
{
    st[a][b]=1;
    hh=tt=0;
    q[tt++]={a,b};
    while(hh<tt)
    {
        auto t=q[hh++];
        for(int i=t.x-1;i<=t.x+1;i++)
        {
            for(int j=t.y-1;j<=t.y+1;j++)
            {
                if(i==t.x&&j==t.y) continue;
                if(i<1||i>n||j<1||j>n) continue;
                if(g[i][j]>g[t.x][t.y]) h++;
                else if(g[i][j]<g[t.x][t.y]) v++;
                else 
                {
                    if(st[i][j]) continue;//因为要看非连通位置，所以在加入队列之前再判断是否出现过
                    q[tt++]={i,j};
                    st[i][j]=1;
                }
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) 
            scanf("%d",&g[i][j]);
 
    int sf=0,sg=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!st[i][j])
            {
                int h=0,v=0;
                bfs(i,j,h,v);
                if(h&&v) continue;
                else if(v) sf++;//有比它矮的
                else if(h) sg++;//有比它高的
                else sf++,sg++;
            }
        }
    }
    cout<<sf<<" "<<sg;
}

最短路问题

这里的最短路问题有个条件就是每一步的权重都相等（未必都是1，只要相等即可），根据bfs中队列的性质，每个位置第一次被扫到的时候，那么进行的操作数或者走过的路径就是最短路。

1076. 迷宫问题（活动 - AcWing）

 

思路：这里输出最短路，我们的处理就是记录每个位置是由谁转移而来的。相当于将st数组变成pair<int,int>的类型，我们因为这里的左边是从0开始的，那么我们可以将st初始化成-1，memset(st,-1,sizeof st),那么每个st的第一位和第二位就是-1，我们查找的时候只用判断一下就知道这个位置是否已经被搜过了。另外免得再存一遍，我们可以从终点往起点搜。

而且这里的搜索也不再是遍历了，而是从某一个点开始搜。

#include<bits/stdc++.h>
using namespace std;
#define x first 
#define y second
typedef pair<int,int> pii;
pii q[1000010];
pii st[1010][1010];
int hh,tt;
int n;
int g[1010][1010];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void bfs(int a,int b)
{
    memset(st,-1,sizeof st);
    st[a][b]={a,b};
    hh=tt=0;
    q[tt++]={a,b};
    while(hh<tt)
    {
        auto t=q[hh++];
        for(int i=0;i<4;i++)
        {
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(nx<0||nx>=n||ny<0||ny>=n) continue;
            if(st[nx][ny].x!=-1) continue;
            if(g[nx][ny]==1) continue;
            st[nx][ny]={t.x,t.y};
            q[tt++]={nx,ny};
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++) 
            scanf("%d",&g[i][j]);
    bfs(n-1,n-1);
    pii e(0,0);//表示定义一个名为e的pair<int,int>类型的变量，初值赋为{0，0}
    while(1)
    {
        cout<<e.x<<" "<<e.y<<endl;
        if(e.x==n-1&&e.y==n-1) break;
        e=st[e.x][e.y];
    }
}

188. 武士风度的牛(188. 武士风度的牛 - AcWing题库)

 

思路：就相当于马走日，从一个点到另一个点最少多少步，那么就是一个bfs宽搜问题。 不过这里需要注意的是，中间有障碍物可能有些位置需要判断一下。

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
pii q[40010];
int n,m,hh,tt;
char s[200][200];
int ex,ey;
int d[200][200];
int st[200][200];
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
void bfs(int sx,int sy)
{
    memset(d,0x3f,sizeof d);
    d[sx][sy]=0;
    st[sx][sy]=1;
    hh=tt=0;
    q[tt++]={sx,sy};
    while(hh<tt)
    {
        auto t=q[hh++];
        for(int i=0;i<8;i++)
        {
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m) continue;
            if(st[nx][ny]) continue;
            if(s[nx][ny]=='*') continue;
            q[tt++]={nx,ny};
            d[nx][ny]=d[t.x][t.y]+1;
            st[nx][ny]=1;
        }
    }
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    int sx,sy;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='K') sx=i,sy=j;
            if(s[i][j]=='H') ex=i,ey=j;
        }
    }
    bfs(sx,sy);
    //printf("%d %d %d %d\n",sx,sy,ex,ey);
    cout<<d[ex][ey];
}

 ps：这题的陷阱在于先输入列数再输入行数，记得交换一下。

1100. 抓住那头牛（活动 - AcWing）

这里虽然是在数轴上，但仍旧是每个点有三种操作，求到另一个点的最短路，看着有点像贪心，但是实际上就是bfs暴搜。另外要注意一点，当牛在左边时，+1和2倍的操作都没有意义了，所以右边界实际上是2e5。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
int n,m;
int d[N],st[N],q[N],hh,tt;
void bfs(int s)
{
    st[s]=1;
    d[s]=0;
    hh=tt=0;
    q[tt++]=s;
    while(hh<tt)
    {
        auto t=q[hh++];
        if(0<=t+1&&t+1<=N&&!st[t+1]) 
        {
            d[t+1]=d[t]+1;
            st[t+1]=1;
            q[tt++]=t+1;
        }
        if(0<=t-1&&t-1<=N&&!st[t-1]) 
        {
            d[t-1]=d[t]+1;
            st[t-1]=1;
            q[tt++]=t-1;
        }
        if(0<=2*t&&2*t<=N&&!st[2*t]) 
        {
            d[2*t]=d[t]+1;
            st[2*t]=1;
            q[tt++]=2*t;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    bfs(n);
    cout<<d[m];
}

 ps:一定要注意左边界可以到0.