一位虔诚的软微信徒头像
搜索算法详解(3)Floodfill 问题封面图

搜索算法详解(3)Floodfill 问题

欢迎来到我的频道 [【点击跳转专栏】]在这里插入图片描述
作者说:我想说 基础 不等于 简单 ;算法能力不是一蹴而就的,而是来自日积月累的积累和练习!积小流终成江海,诸君 加油!!

0. 算法介绍

Floodfill 算法,又称漫水填充,像素法,本质是在寻找具有相同性质的联通块。

即 寻找性质相同的连通块,可以利用bfs、dfs解决,下图为4连通:
在这里插入图片描述

1. Lake Counting(模版题)

https://www.luogu.com.cn/problem/P1596

在这里插入图片描述

遍历整个矩阵,当遇到一个没有标记过的水坑时:

  • 计数;
  • 然后用 bfs 或者 dfs 将整个湖全都标记一下。 整个矩阵遍历一遍,就能得出湖的数量。

关于对角线如何写方向向量,如图:
在这里插入图片描述

dfs代码版本:

#include<bits/stdc++.h>
using namespace std;
const int N=110;
char a[N][N];   // 存储地图,W代表水坑
int n,m;        // n行 m列
// 8个方向:上下左右 + 4个斜向(八连通)
int dx[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy[]={1, -1, 0, 0, 1, -1, 1, -1};
bool st[N][N];  // 标记这个位置是否已经被访问过

// dfs:把和(i,j)连通的所有水坑全部标记访问
void dfs(int i,int j)
{
    st[i][j]=true;  // 当前点标记为已访问
    // 枚举8个方向
    for(int k=0;k<8;k++)
    {
        int x=i+dx[k],y=j+dy[k];
        // 边界合法 + 是水坑W + 没有访问过
        if(x>=1&&y>=1&&x<=n&&y<=m&&a[x][y]=='W'&&st[x][y]==false)
        {
            dfs(x,y);
        }
    }
}
int main()
{
    cin>>n>>m;
    // 读入地图
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    
    int ret=0;  // 记录水坑(湖)的数量
    // 遍历整个矩阵
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            // 找到一个没访问过的水坑,说明新发现一个湖
            if(a[i][j]=='W'&&st[i][j]==false)
            {
                ret++;
                dfs(i,j); // dfs把这片连通的水坑全部标记
            }
        }
    }
    cout<<ret<<endl;
    return 0;
}

bfs代码版本:

#include<bits/stdc++.h>
using namespace std;
const int N=110;
typedef pair<int,int> PII;
char a[N][N];   // 存储地图,'W'代表水坑
int n,m;        // n行 m列
// 8个方向:上下左右 + 四个斜向(八连通)
int dx[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy[]={1, -1, 0, 0, 1, -1, 1, -1};
bool dist[N][N];// 标记该点是否已经访问过

// BFS:把(i,j)所在整片连通水坑全部标记访问
void bfs(int i,int j)
{
    queue<PII> q;
    q.push({i,j});
    dist[i][j]=true;  // 起点打上访问标记
    while(q.size())
    {    
      auto t=q.front();
      q.pop();
      int a1=t.first,b1=t.second; // 当前点坐标
      for(int k=0;k<8;k++) // 枚举8个方向
      {
        int x=a1+dx[k],y=b1+dy[k]; // 算出相邻点坐标
        // 条件:坐标不越界、是水坑、还没有访问过
        if(x>=1&&y>=1&&x<=n&&y<=m&&a[x][y]=='W'&&dist[x][y]==false)
        {
            q.push({x,y});
            dist[x][y]=true;  // 入队立刻标记,防止重复入队
        }
      }
    }
}
int main()
{
    cin>>n>>m;
    // 读入整张地图
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    int ret=0; // 记录湖(连通水坑)的总数
    // 遍历矩阵每一个格子
    for(int i=1;i<=n;i++)
    {
       for(int j=1;j<=m;j++)
       {
           // 找到一个未访问的水坑,说明发现新湖
           if(a[i][j]=='W'&&dist[i][j]==false)
           {
               ret++;
               bfs(i,j); // BFS把这片连通区域全部标记
           }
       }
    }
    cout<<ret<<endl;
    return 0;
}

2. 填涂颜⾊

https://www.luogu.com.cn/problem/P1162 请添加图片描述

正难则反:直接找出被 1 包围的 0 是很困难的,因为很难确定当前搜索到的这个 0 是否是被包围的。但是,我们如果从边缘的 0 开始搜索,搜索到的 0 一定是没有被包围的。
在这里插入图片描述
因此,我们可以从边缘的 0 开始搜索,标记所有与边缘 0 相连的连通块。那么,没有被标记过的 0 就是被包围的。


小技巧:

  • 我们可以把整个矩阵的外围包上一层 0,这样只用从 [0,0] 位置开始搜即可。不用遍历第一行、第一列,最后一行以及最后一列,也就是不需要写4个for循环了
    在这里插入图片描述

这里我直接用dfs写了 ,毕竟dfs会写 bfs这种更简单的方式只会更好写。

#include<bits/stdc++.h>
using namespace std;
const int N=35;
int a[N][N];     // 存储矩阵,1是墙,0是空;下标范围0~n+1,外围自带一层0
bool st[N][N];   // 标记该位置是否和外界连通(被DFS搜到)
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int n;

// DFS:从(i,j)出发,标记所有和外界连通的0
void dfs(int i,int j)
{
    st[i][j]=true;  // 当前点标记为已访问
    for(int k=0;k<4;k++)  // 枚举上下左右4个方向(四连通)
    {
        int x=i+dx[k],y=j+dy[k];
        // 边界合法:0~n+1,是0,且还没标记
        if(x>=0&&y>=0&&x<=n+1&&y<=n+1&&a[x][y]==0&&st[x][y]==false)
        {
            dfs(x,y);
        }
    }
}
int main()
{
    cin>>n;
    // 读入中间n*n的矩阵
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    // 正难则反技巧:外围包一层0,直接从(0,0)开始搜所有连通外界的0
    dfs(0,0);

    // 遍历输出结果
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]) 
                cout<<1<<" ";        // 本身是墙,输出1
            else if(st[i][j]) 
                cout<<0<<" ";        // 是0,并且连通外界,没有被包围,输出0
            else 
                cout<<2<<" ";        // 是0,且不和外界连通,被1包围,输出2
        }
        cout<<endl;
    }
    return 0;
}

转载自 CSDN-专业IT技术社区

原文链接:https://blog.csdn.net/Fcy648/article/details/170856530

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数:0
关注数:0
粉丝:0
文章:0
关注标签:0
加入于:--