P6866 Emacs 题解

ACrazySteve · 2021-07-21 23:58:16 · 个人记录

这是本蒟蒻写的第一篇题解。。。
可能还有一些不恰当的地方，希望Dalao们能容忍

Flood Fill

这是一道Flood Fill算法的模板(?)题，Flood Fill算法,(也称为种子填充——Seed Fill)，这个算法就是专门填充一块区域的（类似mspaint里的油漆桶，可以填充一个色块），在这题中，每个长方体都是不接壤的，所以可以直接用Flood Fill算法暴力填充每一个长方体，一共填充了多少次，就有多少个长方体。于是废话不多说，直接上代码

#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,0,1,-1};//方向数组，懂得都懂。。。
int dy[4]={1,-1,0,0};
int n,m;
char g[1001][1001];
void flood_fill(int x,int y)
{
    g[x][y]='.';//先把这里直接改为'.'以免重复填充、导致WA
    for(int i=0;i<=3;i++)//这里开始填充周围的部分
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&g[xx][yy]=='*')//判断边界
        {
            flood_fill(xx,yy);//继续填充
        }
    }
}
int cnt;
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    cin >> n >> m;
    memset(g,'.',sizeof(g));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin >> g[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(g[i][j]=='*') g[i][j]='.',cnt++,flood_fill(i,j);//检测到有新的长方形，长方体个数+1
        }
    }
    cout << cnt;//输出长方体个数
    return 0;//轻松地结束
//  exit(0);
}

推荐一道Flood Fill的题 USACO Open 2008 Bronze里的 最好的草 洛谷似乎没有收录这道题。。。 可以直接上USACO做这道题或者到NOI OPENJUDGE上面做这道题