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

C++算法

Flood Fill 算法实战：图像渲染与岛屿问题解析

Flood Fill 算法利用 DFS 或 BFS 遍历连通区域。通过图像渲染、岛屿数量、岛屿最大面积、被围绕区域四道经典题，演示如何标记访问状态、处理边界条件及统计连通分量大小。掌握此模式可解决大量网格遍历问题。

全栈工匠发布于 2026/3/28更新于 2026/4/251 浏览

Flood Fill 算法实战：图像渲染与岛屿问题解析

Flood Fill（洪水填充算法）是一种用于确定多维数组中给定节点连通区域的经典算法。其核心在于从种子点出发，向四周扩散，仅填充满足特定条件的相邻节点，并通过标记已访问位置避免重复处理。

一、图像渲染

题目描述

给定一个 m*n 的二维整数数组 image，以及起始坐标 [sr, sc] 和目标颜色 color。要求将起始位置及其上下左右四个方向上相邻且颜色相同的像素点全部染成目标颜色。

思路分析

这道题是 Flood Fill 最直接的体现。我们只需要从起点开始进行一次深度优先搜索（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];
            // 边界检查 & 颜色匹配
            if (x >= 0 && x < m && y >= 0 && 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;
        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();
        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();
        // 1. 处理边界，标记与边缘相连的 O
        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);
        }
        // 2. 修改内部未被标记的 O 为 X
        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);
            }
        }
    }
};