Flood Fill 算法实战：从图像渲染到岛屿问题 | 极客日志

C++算法

Flood Fill 算法实战：从图像渲染到岛屿问题

Flood Fill 算法利用 DFS 或 BFS 遍历连通区域。通过图像渲染、岛屿数量、最大面积及被围绕区域四个经典案例，演示如何应用该算法解决网格连通性问题。重点讲解边界处理与状态标记技巧，帮助读者掌握核心逻辑。

忘忧发布于 2026/3/23更新于 2026/4/273 浏览

Flood Fill 算法实战：从图像渲染到岛屿问题

前言

Flood Fill（泛洪填充）是处理网格连通区域的基础算法，常用于图像处理或图论中的连通分量统计。其核心逻辑是从种子点出发，向四周扩散，标记所有满足条件的相邻节点。

一、图像渲染

题目解析

给定一个 m * n 的二维数组，从起始位置 [sr, sc] 开始，将上下左右四个方向上相邻且与起始位置初始颜色相同的像素点进行染色，直到没有其他原始颜色的相邻像素。

图像渲染示意图

解题思路

这道题本质上是典型的深度优先搜索（DFS）。从起点开始递归遍历，改变当前节点颜色并继续探索邻居。

注意：如果起始位置的颜色已经等于目标颜色，直接返回原数组即可，避免无效操作。

代码实现

class Solution {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
public:
    void dfs(vector<vector<int>>& image, int i, int j, int srcColor, int destColor) {
        // 变色
        int m = image.size();
        int n = image[0].size();
        image[i][j] = destColor;
        
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
             (x >=  && x < m && y >=  && y < n && image[x][y] == srcColor) {
                (image, x, y, srcColor, destColor);
            }
        }
    }

    vector<vector<>> (vector<vector<>>& image,  sr,  sc,  color) {
         (image[sr][sc] != color) {
            (image, sr, sc, image[sr][sc], color);
        }
         image;
    }
};

class Solution {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    bool vis[300][300];
public:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        vis[i][j] = true;
        int m = grid.size(), n = grid[0].size();
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1') {
                dfs(grid, x, y);
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ret = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !vis[i][j]) {
                    dfs(grid, i, j);
                    ret++;
                }
            }
        }
        return ret;
    }
};

class Solution {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    bool vis[50][50];
public:
    void dfs(vector<vector<int>>& grid, int i, int j, int& cnt) {
        ++cnt;
        vis[i][j] = true;
        int m = grid.size();
        int n = grid[0].size();
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]) {
                dfs(grid, x, y, cnt);
            }
        }
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ret = 0, cnt = 0;
        int m = grid.size(), n = grid[0].size();
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !vis[i][j]) {
                    dfs(grid, i, j, cnt);
                    ret = max(ret, cnt);
                    cnt = 0;
                }
            }
        }
        return ret;
    }
};

class Solution {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[210][210];
public:
    void dfs(vector<vector<char>>& board, int i, int j, bool isChange = false) {
        if (isChange) board[i][j] = 'X';
        vis[i][j] = true;
        int m = board.size();
        int n = board[0].size();
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && y >= 0 && x < m && y < n && !vis[x][y] && board[x][y] == 'O') {
                dfs(board, x, y, isChange);
            }
        }
    }

    void solve(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        memset(vis, 0, sizeof(vis));
        
        // 处理边界
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O' && !vis[i][0]) dfs(board, i, 0);
            if (board[i][n - 1] == 'O' && !vis[i][n - 1]) dfs(board, i, n - 1);
        }
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O' && !vis[0][i]) dfs(board, 0, i);
            if (board[m - 1][i] == 'O' && !vis[m - 1][i]) dfs(board, m - 1, i);
        }

        // 修改内部
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O' && !vis[i][j]) {
                    dfs(board, i, j, true);
                }
            }
        }
    }
};