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

C++算法

Flood Fill 算法详解：从图像渲染到岛屿问题

Flood Fill 算法利用深度优先搜索遍历连通区域。本文结合图像渲染、岛屿数量、最大面积及被围绕区域四个经典题目，演示如何应用该算法解决二维网格中的连通性问题，重点讲解 DFS 实现细节与边界处理技巧。

嘘发布于 2026/3/260 浏览

Flood Fill 算法详解：从图像渲染到岛屿问题

Flood Fill 算法实战

Flood Fill（泛洪填充）是处理连通区域的基础算法，常用于图像处理或网格遍历。其核心逻辑是从种子点出发，向四周扩散，根据特定条件标记相邻节点。

一、图像渲染

题目描述

给定一个二维数组表示的图像，从起始位置 [sr, sc] 开始，将上下左右四个方向上相邻且颜色相同的像素点染成目标颜色。

图像渲染示意图

思路解析

这道题本质上是深度优先搜索（DFS）。从起点开始递归染色，直到无法继续扩展。这里有个细节要注意：如果起始位置的颜色和目标颜色相同，直接返回原数组即可，避免无效操作。

代码实现

class Solution {
public:
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    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];
            if (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 {
public:
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    bool vis[300][300];

    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 {
public:
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    bool vis[50][50];

    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 {
public:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[210][210];

    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();
        // 处理边界，标记安全区域
        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);
                }
            }
        }
    }
};