洪水填充

洪水填充是搜索的一个简单应用。一张图上有多个区域，不同的区域用不同颜色区分，同一个区域的所有点的颜色都是相同的。给定图上的一个点，称为种子点，然后从种子点出发，把种子点所属的封闭区域用新颜色填充，这就是洪水填充。

洪水填充的编程用BFS和DFS都可以。洪水扩散过程符合BFS的原理，不过用DFS编码更简单。

例题

[hdu-1312](问题 - 1312 (hdu.edu.cn))

代码模板

//#include <bits/stdc++.h>
#include <iostream>
#include <string.h>
using namespace std;
#define LL long long
const int N=30;
char a[N][N];
int n,m;
int st[N][N];
int sum;
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

void dfs(int x,int y)
{
    int dx,dy;
    for(int i=0;i<4;i++)
    {
        dx=x+d[i][0];
        dy=y+d[i][1];
        if(dx>=0&&dx<m&&dy>=0&&dy<n&&st[dx][dy]==0&&a[dx][dy]=='.')
        {
            sum++;
            st[dx][dy]=1;
            dfs(dx,dy);
        }
    }
}

int main(){
    while(cin>>n>>m)
    {
        sum=0;
        memset(st,0,sizeof st);
        for(int i=0;i<m;i++)cin>>a[i];
        for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
        {
            if(a[i][j]=='@')
            {
                sum++;
                dfs(i,j);
                cout<<sum<<endl;
                break;
            }
        }
    }
    return 0;
}

​

[poj-2227](2227 -- The Wedding Juicer (poj.org))

思路：通过"四周堵中央"的思路。从最外围的一圈开始找最小的位置，进行bfs搜索如果搜索到的位置的值小于该位置的值，把两者的差值记录，在把搜索到的值变为该位置的值，如果大于则不变。

代码模板

//#include <bits/stdc++.h>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define LL long long
#define x first
#define y second
typedef pair<int,int> PII;
const int N=310;
int a[N][N],st[N][N];
int n,m;
int sum;
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct Node
{
    int x,y;
    int w;
    bool operator< (const Node &W)const
    {
        return w>W.w;
    }
}nd[N];

priority_queue<Node> q;

void bfs()
{
    int tx,ty;
    while(!q.empty())
    {
        Node t=q.top();
        q.pop();
        tx=t.x;
        ty=t.y;
        for(int i=0;i<4;i++)
        {
            int dx,dy;
            dx=tx+d[i][0];
            dy=ty+d[i][1];
            if(dx>0&&dx<=m&&dy>0&&dy<=n&&st[dx][dy]==0)
            {
                st[dx][dy]=1;
                Node tt;
                tt.x=dx,tt.y=dy,tt.w=a[dx][dy];
                if(t.w>tt.w)sum+=t.w-tt.w,tt.w=t.w;
                q.push(tt);
            }
        }
    }

}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    {
        cin>>a[i][j];
        if(i==1||j==1||i==m||j==n)
        {
            Node t;
            st[i][j]=1;
            t.x=i;
            t.y=j;
            t.w=a[i][j];
            q.push(t);
        }
    }
    bfs();
    cout<<sum;
    return 0;

}

[lg-1514]([P1514 NOIP2010 提高组] 引水入城 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

思路：对第一行每一个点进行dfs，得到每一个点在最后一行所能覆盖的线段，对每段线段求最大值，通过标记函数可以判断最后一行是否都搜索过。对于得到的线段具有连续性，因为如果不是连续，我么们可以很容易的证明这个点无法到达（它所在联通块边界一定高于相邻点）

代码模板

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=510;
int a[N][N],l[N][N],r[N][N];
int st[N][N];
int  n,m;
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

void dfs(int x,int y)
{
    st[x][y]=1;
    int dx,dy;
    for(int i=0;i<4;i++)
    {
        dx=x+d[i][0];
        dy=y+d[i][1];
        if(dx>0&&dx<=n&&dy>0&&dy<=m&&a[dx][dy]<a[x][y])
        {
            if(!st[dx][dy])
            dfs(dx,dy);
            l[x][y]=min(l[x][y],l[dx][dy]);
            r[x][y]=max(r[x][y],r[dx][dy]);
        }
    }
}
int main(){
    cin>>n>>m;
    memset(l,0x3f,sizeof l);
    for(int i=1;i<=m;i++)
    l[n][i]=r[n][i]=i;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        cin>>a[i][j];
    }
    for(int i=1;i<=m;i++)
    if(!st[1][i])dfs(1,i);
    int cnt=0;
    bool flag=false;
    for(int i=1;i<=m;i++)
    if(!st[n][i])
    {
        flag=true;
        cnt++;
    }
    if(flag)
    {
        cout<<0<<endl<<cnt;
        return 0;
    }
    int left=1;
    while(left<=m)
    {
        int maxi=0;
        for(int i=1;i<=m;i++)
        if(l[1][i]<=left)
        maxi=max(maxi,r[1][i]);
        cnt++;
        left=maxi+1;
    }
    cout<<1<<endl<<cnt;
    return 0;
}

练习

hdu：5319/4574/1240/6113

洛谷：1506/1162/1649

poj：1979/3026/2157

声明

本文是《算法竞赛》的笔记，仅此而已。