Flood Fill Lv.2

· · 个人记录

这难度要都是这样我一天能干十节

一、算法介绍

想象一个这样的模型：有一张地图，上面有一些洼地，有一些高地。任选一个点，在其上方悬挂一个无尽水源，开始往这个格子里灌水。每过一个单位时间，水会漫进周围的格子，只能覆盖洼地，不能覆盖高地，最终整块区域的洼地都被水填满。这样的模型我们称为 \mathrm{Flood\space Fill} 模型。

当然，\mathrm{Flood\space Fill} 模型用 \mathrm{dfs,bfs} 都可以写，但是用 \mathrm{dfs} 会涉及到爆栈的问题，风险很大，因此一般推荐用 \mathrm{bfs} 解决这个问题。

那这个算法有什么用呢？它可以在线性时间内求出在经过一段时间后，某个点所在的连通块。

二、\mathrm{Flood\space Fill} 通用模板

#include <bits/stdc++.h>
using namespace std;
const int N=10010;
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int n,m;
int g[N][N];
bool st[N][N];
void bfs(int sx,int sy)
{
    queue <PII> q;
    q.push({sx,sy});
    st[sx][sy]=true;
    while (q.size())
    {
        PII t=q.front();
        q.pop();
        // On 8-connected graph :
        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 (st[i][j])
                    continue;
                // other judgement
                // do something ...
                q.push({i,j});
                st[i][j]=true;
            }
        // On 4-connected graph :
        for (int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            // repeat steps above
        }
    }
    return;
}
int main()
{
    // input and process ...
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (!st[i][j])
            {
                // do something ...
                bfs(i,j);
                // do something ...
            }
    // process and output ...
}

这些在后文的例题中基本都没有变化，最多因题目而对顺序进行一些微小的调整。

三、\mathrm{Flood\space Fill} 算法的应用

1. 应用 1 ：计算地图中连通块的数量

我们从上到下、从左到右地遍历整张地图，发现了是我们该统计的区域，并且该点还没有被访问过的话，我们就从这个格子开始进行 \mathrm{Flood\space Fill} ，然后将整个连通块的点全部标记一遍后，累加进答案，再从刚刚的地方继续往下遍历地图。遍历结束后求得答案。

I. 例题 1. 池塘计数

模板题，注意在写搜索有关的题目都要注意各种边界细节问题！

代码实现：

// AcWing 1097. 池塘计数
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N=1010;
int n,m,ans;
char g[N][N];
bool st[N][N];
void bfs(int x,int y)
{
    queue <PII> q;
    q.push({x,y});
    st[x][y]=true;
    while (q.size())
    {
        PII t=q.front();
        q.pop();
        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 (g[i][j]!='W' || st[i][j])
                    continue;
                q.push({i,j});
                st[i][j]=true;
            }
    }
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%s",g[i]+1);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (g[i][j]=='W' && !st[i][j])
            {
                bfs(i,j);
                ans++;
            }
    printf("%d\n",ans);
    return 0;
}

2. 应用 2 ：求每个连通块的大小

I. 例题 2. 城堡问题

唯一的不同在于对输入数据的处理和求出最大面积，但这些对能学到这里的我们来说都是小 \mathrm{case} 了吧（逃

代码实现：

// AcWing 1098. 城堡问题
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N=60;
const int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int n,m;
int g[N][N];
bool st[N][N];
int bfs(int sx,int sy)
{
    queue <PII> q;
    q.push({sx,sy});
    st[sx][sy]=true;
    int area=0;
    while (q.size())
    {
        PII t=q.front();
        q.pop();
        area++;
        for (int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if (a<1 || a>n || b<1 || b>m)
                continue;
            if (st[a][b])
                continue;
            if (g[t.x][t.y]>>i&1)
                continue;
            q.push({a,b});
            st[a][b]=true;
        }
    }
    return area;
}
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 area=0,cnt=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (!st[i][j])
            {
                area=max(area,bfs(i,j));
                cnt++;
            }
    printf("%d\n%d\n",cnt,area);
    return 0;
}

3. 应用 3 ：处理连通块与周围部分的关系

I. 例题 3. 山峰和山谷

代码实现：

// AcWing 1106. 山峰和山谷
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N=1010;
int n;
int g[N][N];
bool st[N][N];
void bfs(int sx,int sy,bool &has_higher,bool &has_lower)
{
    queue <PII> q;
    q.push({sx,sy});
    st[sx][sy]=true;
    while (q.size())
    {
        PII t=q.front();
        q.pop();
        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])
                {
                    if (g[i][j]>g[t.x][t.y])
                        has_higher=true;
                    else
                        has_lower=true;
                }
                else if (!st[i][j])
                {
                    q.push({i,j});
                    st[i][j]=true;
                }
            }
    }
    return;
}
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 peak=0,valley=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (!st[i][j])
            {
                bool has_higher=false,has_lower=false;
                bfs(i,j,has_higher,has_lower);
                if (!has_higher)
                    peak++;
                if (!has_lower)
                    valley++;
            }
    printf("%d %d\n",peak,valley);
    return 0;
}