开发者社区> 辰Chen> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Flood Fill(一)

简介: 复习acwing算法提高课的内容,本篇为讲解算法:Flood Fill,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
+关注继续查看

文章目录

前言

一、Flood Fill

二、例题,代码

AcWing 1097. 池塘计数

本题分析

AC代码

AcWing 1098. 城堡问题

本题分析

AC代码

AcWing 1106. 山峰和山谷

本题分析

AC代码

三、时间复杂度


前言

复习acwing算法提高课的内容,本篇为讲解算法:Flood Fill,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。


一、Flood Fill

Flood Fill算法是搜索的算法中的一种,用来解决类似田地覆盖这么一系列问题,算法核心是BFS


二、例题,代码

AcWing 1097. 池塘计数

本题链接:AcWing 1097. 池塘计数

本博客提供本题截图:

image.png

image.png

本题分析

本题就是水的覆盖问题,可以用bfs去解,核心思路就是从第一行第一列(即图中的第一个元素)去遍历,这里需要一个bool st[N][N]数组去记录这个点有没有被遍历过,如果被遍历过的话直接跳过这个点就可以了,我们每次挑选合适的点放入到队列之中,并用这个点作为“母点”去向8个方向去扩散,这里扩散的时候没有使用向量的方法,对于四扩散向量的方法很简单,但是对于8个方向的扩散,显然这里用一个二重for循环可以比较容易的解决问题,注意特判for循环中的条件,对于不符合条件的点continue

if (t.x == i && t.y == j) continue;      //遍历到这个点的时候continue
if (i < 0 || i >= n || j < 0 || j >= m) continue; //越界的时候continue
if (g[i][j] == '.' || st[i][j]) continue;   //这个点如果不是水的话或者这个点之前被遍历过的话就continue

这样三个if判断之后的点一定是符合题意可以扩散水的点,那么就把这个点放到队列中,并把这个点的bool值变成true

q[++ tt] = {i, j};
st[i][j] = true;

AC代码

#include <cstdio>
#include <algorithm>
#include <map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

PII q[M];
char g[N][N];
bool st[N][N];
int n, m, cnt;

void bfs(int x1, int y1)
{
    int hh = 0, tt = 0;
    q[0] = {x1, y1};
    st[x1][y1] = true;
    
    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 (t.x == i && t.y == j) continue;
                if (i < 0 || i >= n || j < 0 || j >= m) continue;
                if (g[i][j] == '.' || st[i][j]) continue;
                
                q[++ tt] = {i, j};
                st[i][j] = true;
            }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
    
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ ) 
            if (!st[i][j] && g[i][j] == 'W')
            {
                bfs(i, j);
                cnt ++;
            }
            
    printf("%d", cnt);
    
    return 0;
}

AcWing 1098. 城堡问题

本题链接:AcWing 1098. 城堡问题

本博客提供本题截图:

image.png

image.png

本题分析

和上一个题目基本一致,不同的有两点,一点是上一个题是八扩散,用的是两重for循环,这个题是四扩散,用的是向量,第二个不同是如何把数字形象化:位运算。

AC代码

#include <cstdio>
#include <map>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 55, M = N * N;

PII q[M];
int g[N][N];
bool st[N][N];
int n, m;

int bfs(int x1, int y1)
{
    int area = 0;
    
    int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
    
    int hh = 0, tt = 0;
    q[0] = {x1, y1};
    st[x1][y1] = true;
    
    while (hh <= tt)
    {
        auto t = q[hh ++];
        area ++;
        
        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (g[t.x][t.y] >> i & 1) continue;
            if (st[a][b]) continue;
            
            q[++ tt] = {a, b};
            st[a][b] = true;
        }
    }
    
    return area;
}

int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < m ; j ++ )
            scanf("%d", &g[i][j]);
            
    int cnt = 0, area = 0;
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < m; j ++ )
            if (!st[i][j])
            {
                cnt ++;
                area = max (area, bfs(i, j));
            }
        
    printf("%d\n%d\n", cnt, area);
    
    return 0;
}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
[20170516]nvl与非NULL约束.txt
[20170516]nvl与非NULL约束.txt --前几天做的测试http://blog.itpub.net/267265/viewspace-2137853/,实际上差异没有这个大,因为第2个多数是常量.
795 0
centos7精简版(minimal)killall: command not found
  centos7精简版(minimal)运行killall命令提示 command not found   是由于没有安装psmisc所致   Psmisc软件包包含三个帮助管理/proc目录的程序。
856 0
图像处理之泛洪填充算法(Flood Fill Algorithm)
泛洪填充算法(Flood Fill Algorithm) 泛洪填充算法又称洪水填充算法是在很多图形绘制软件中常用的填充算法,最熟悉不过就是 windows paint的油漆桶功能。算法的原理很简单,就是从一个点开始附近像素点,填充成新 的颜色,直到封闭区域内的所有像素点都被填充新颜色为止。
1268 0
+关注
辰Chen
CSDN人工智能领域优质创作者,华为云&middot;云享专家,CCF-TYUT President-designate
719
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载