Flood Fill

池塘计数

知识点

在池塘中存在两种连通方式，分别为：
- 四联通：只有通过边数才可以连通
- 八连通：通过端点也可以连通

解题思路

从前往后一行一行扫描
如果扫描到了一个还没有被标记的水，那么就执行Flood Fill算法
Flood Fill算法指的是从一个起始点开始，通过扩散的方式标记所有与起始点相连的相同类型的点
- 具体步骤如下：
  1. 从起始点开始，将其标记为已访问
  2. 将起始点加入队列
  3. 当队列不为空时，取出队首元素，检查其所有相邻位置（在本题中是八个方向）
  4. 如果相邻位置是水且未被访问过，则将其标记为已访问并加入队列
  5. 重复步骤3-4直到队列为空
- 这样就能找到与起始点相连的所有水域，构成一个完整的池塘
- 每执行一次完整的Flood Fill，就意味着找到了一个新的池塘

实现代码

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

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

int n, m;
// 输入的地图
char g[N][N];
// 用队列存储的可扩展的水结点
PII q[M];
// 存储该点是否被遍历过
bool st[N][N];

void bfs(int sx, int sy){
    // 模拟队列
    // 初始化队头和队尾
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = true;
    while(hh <= tt){
        PII t = q[hh ++];

        // 八连通
        // 遍历当前点周围的8个相邻位置
        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 < 0 || i >= n || j < 0 || j >= m)
                    continue;

                // 跳过非水域或已访问过的点
                if(g[i][j] == '.' || st[i][j])
                    continue;

                // 标记该点已访问并加入队列
                st[i][j] = true;
                q[++ tt] = {i, j};
            }
    }

}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++)
        scanf("%s", g[i]);

    int cnt = 0;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            if(g[i][j] == 'W' && !st[i][j]){
                bfs(i, j);
                cnt ++;
            }

    cout << cnt << endl;
    return 0;
}

AcWing算法提高课搜索基础知识

Flood Fill

池塘计数

知识点

解题思路

实现代码

Enjoy Reading This Article?