数据结构与算法 - 泛洪填充算法

发表于 更新于 分类于

泛洪填充算法 (Flood Fill Algorithm) 泛洪填充算法又称洪水填充算法是在很多图形绘制软件中常用的填充算法，最熟悉不过就是 windows paint 的油漆桶功能。算法的原理很简单，就是从一个点开始附近像素点，填充成新的颜色，直到封闭区域内的所有像素点都被填充新颜色为止。泛红填充实现最常见有四邻域像素填充法，八邻域像素填充法，基于扫描线的像素填充方法。根据实现又可以分为递归与非递归方法，递归方法一般通过深度优先搜索进行实现，非递归方法一般通过广度优先搜索或并查集实现。

泛洪填充题目解析

深度优先搜索

200. 岛屿数量

题目描述：

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

示例 1：

    输入：grid = [
        ["1","1","1","1","0"],
        ["1","1","0","1","0"],
        ["1","1","0","0","0"],
        ["0","0","0","0","0"]
    ]
    输出：1

深度优先搜索解法：

class Solution {
private:
    int M, N;
    const vector<vector<int>> dis{{1,0},{-1,0},{0,1},{0,-1}};
    bool isvalid(int i, int j) {
        return i >= 0 && j >= 0 && i < M && j < N;
    }
    void markIand(vector<vector<char>>& grid, int i, int j) {
        grid[i][j] = '0';
        for (auto &d : dis) {
            int x = i + d[0], y = j + d[1];
            if (isvalid(x, y) && grid[x][y] == '1') markIand(grid, x, y);
        }
        return;
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int num = 0;
        M = grid.size();
        N = grid[0].size();
        /* 寻找未发现的岛屿 */
        for (int i = 0; i < M; i++) for(int j = 0; j < N; j++) {
            if (grid[i][j] == '1') { /* 找到新岛屿 进行标记 */
                markIand(grid, i, j);
                num++;
            }
        }
        return num;
    }
};

广度优先搜索

733. 图像渲染

题目描述：

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，
接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，
重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例 1:

    输入: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
    输出: [[2,2,2],[2,2,0],[2,0,1]]
    解析: 在图像的正中间，(坐标(sr,sc)=(1,1)),
          在路径上所有符合条件的像素点的颜色都被更改成2。
          注意，右下角的像素没有更改为2，
          因为它不是在上下左右四个方向上与初始点相连的像素点。

广度优先搜索解法：

class Solution {
private:
    int M, N;
    const vector<vector<int>> dis{{1,0},{-1,0},{0,1},{0,-1}};
    bool isvalid(int i, int j) {
        return i >= 0 && j >= 0 && i < M && j < N;
    }
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int preColor = image[sr][sc];
        if (preColor == newColor) return image;
        M = image.size();
        N = image[0].size();
        deque<pair<int, int>> q;
        q.emplace_back(sr, sc);
        image[sr][sc] = newColor;
        while (!q.empty()) {
            int i = q.front().first, j = q.front().second;
            q.pop_front();
            for (auto & d : dis) {
                int x = i + d[0], y = j + d[1];
                if (isvalid(x, y) && image[x][y] == preColor) {
                    q.emplace_back(x, y);
                    image[x][y] = newColor;
                }
            }
        }
        return image;
    }
};

并查集

1020. 飞地的数量

题目描述：

给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。
移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。
返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1：

    输入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
    输出：3
    解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

示例 2：

    输入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
    输出：0
    解释：所有 1 都在边界上或可以到达边界。

并查集解法：

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int Find(int n) {
        return n == parent[n] ? n : parent[n] = Find(parent[n]);
    }
    void Union(int a, int b) {
        int rootA = Find(a), rootB = Find(b);
        if (rootA != rootB) {
            if (rank[rootA] > rank[rootB]) swap(rootA, rootB);
            parent[rootA] = rootB;
            rank[rootB] += rank[rootA] + 1;
        }
    }
    int Rank(int a) { return rank[Find(a)]; }
};
class Solution {
public:
    int numEnclaves(vector<vector<int>>& A) {
        int M = A.size();
        int N = A[0].size();
        int landCount = 0;
        UnionFind uf(N * M + 1);
#       define INDEX(i,j) ((i) * N + (j))
        for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) {
            if (A[i][j] != 1) continue;
            landCount++;
            if (i == 0 || i == M - 1 || j == 0 || j == N - 1) uf.Union(M * N, INDEX(i,j)); // 边界
            if (i != 0 && A[i - 1][j] == 1) uf.Union(INDEX(i - 1,j), INDEX(i,j)); // 上侧
            if (j != 0 && A[i][j - 1] == 1) uf.Union(INDEX(i,j - 1), INDEX(i,j)); // 左侧
        }
        return landCount - uf.Rank(N * M);
    }
};

泛洪填充算法题目

参考资料