泛洪填充算法

在我们日常的软件开发工作中，经常会遇到看似基础却蕴含着深刻逻辑的问题。Flood Fill（泛洪填充）算法就是这样一个经典的例子。它不仅是图像处理软件（如 Photoshop 中的“油漆桶”工具）的核心，也是我们理解图遍历算法的绝佳切入点。在 2026 年的今天，随着算力的提升和开发范式的演变，我们不仅需要掌握算法本身，更需要从工程化的角度去思考它。

在本文中，我们将深入探讨 Flood Fill 算法的原理，并通过现代 C++ 和 Java 代码实现来巩固我们的理解。更重要的是，我们会分享在真实的生产环境中，如何结合 AI 辅助编程和现代架构设计来优化这一过程，避免常见的陷阱，并探讨相关的性能优化策略。

核心概念与基础实现

给定一个代表图像的二维网格 INLINECODE54b30603，其中每个元素 INLINECODE4431fe69 都是一个表示像素颜色的整数。同时，还有一个坐标 INLINECODEf83c4d24 代表起始像素（第 INLINECODE20793e97 行和第 INLINECODEc4d64c8a 列），以及一个整数 INLINECODEe2f3cc7d，代表要应用的新颜色。

我们需要从像素 (sr, sc) 开始对图像进行泛洪填充（Flood Fill）。这意味着我们必须更改起始像素的颜色，以及所有与它相连且具有与起始像素相同原始颜色的其他像素的颜色。两个像素被认为是相连的，当且仅当它们在水平或垂直方向上相邻（不包括对角线方向）。

#### 经典示例解析

让我们来看一个实际的例子，以帮助我们直观地理解这一过程：

> 输入： sr = 1, sc = 2, newColor = 2, img[][]= [[1, 1, 1, 0], [0, 1, 1, 1], [1, 0, 1, 1]]

> 输出： [[2, 2, 2, 0], [0, 2, 2, 2], [1, 0, 2, 2]]

> 解释： 从值为 1 的像素 (1, 2) 开始，泛洪填充将所有相连的（上、下、左、右）值为 1 的像素更新为 2。(2, 0) 处的像素保持不变，因为它没有与起始像素相连的相邻的 1。

Table of Content

• [方法 1] 使用深度优先搜索 (DFS) – O(m n) 时间和 O(m n) 空间
• [方法 2] 使用广度优先搜索 (BFS) – O(m n) 时间和 O(m n) 空间
• [方法 3] 现代工程实践：递归限制与栈溢出防护 (2026 视角)
• [方法 4] 生产环境优化：扫描线填充算法
• [方法 5] 并行计算与异构加速 (GPU/CUDA)

[方法 1] 使用深度优先搜索 – O(m n) 时间和 O(m n) 辅助空间

这个思路是使用深度优先搜索（DFS），因为 DFS 会在回溯之前深入探索所有相连的单元格。我们需要更改起始像素的颜色，以及所有与其相连且具有相同原始颜色的像素的颜色。

算法思路：

我们可以这样思考：我们从给定的像素 INLINECODE475fae5a 出发，并将其颜色存储为 INLINECODE721288ac。然后，我们从该单元格开始 DFS。对于每个单元格，我们检查其所有四个相邻单元格。如果相邻单元格在网格内并且颜色与 INLINECODEab2819dc 相同，那么意味着该像素也应该填充新颜色。我们将其更新为 INLINECODEa1af7a6a，并递归调用该邻居的 DFS 以继续向外扩散新颜色。如果邻居颜色不同或超出网格边界，我们直接返回，不再深入。一旦所有相连的单元格都被访问过，我们就得到了最终填充后的图像。

代码实现 (C++):

在下面的 C++ 实现中，我们添加了详细的注释来解释每一步的操作。请注意，我们在主函数中增加了一个检查：如果新旧颜色相同，直接返回，这是防止无限递归的关键。

//Driver Code Starts
#include 
#include 
using namespace std;

//Driver Code Ends

/**
 * 深度优先搜索 (DFS) 辅助函数
 * @param img 图像的引用
 * @param x 当前像素的行坐标
 * @param y 当前像素的列坐标
 * @param oldColor 需要被替换的原始颜色
 * @param newColor 将要应用的新颜色
 */
void dfs(vector<vector>& img, int x, int y, int oldColor, int newColor) {
    
    // 边界检查与颜色匹配检查
    // 如果超出边界，或者当前像素颜色不是 oldColor，直接返回
    if (x = img.size() || 
        y = img[0].size() || img[x][y] != oldColor) {
              return; 
    }

    // 核心操作：更新当前像素颜色
    // 我们在访问时立即修改颜色，这样也能起到 visited 数组的作用，防止重复访问
    img[x][y] = newColor;

    // 递归调用：访问四个方向的邻居
    // 顺序：下 -> 上 -> 右 -> 左
    dfs(img, x + 1, y, oldColor, newColor); 
    dfs(img, x - 1, y, oldColor, newColor); 
    dfs(img, x, y + 1, oldColor, newColor); 
    dfs(img, x, y - 1, oldColor, newColor); 
}

/**
 * 泛洪填充主函数
 * @param img 图像二维数组
 * @param sr 起始行
 * @param sc 起始列
 * @param newColor 新颜色
 * @return 填充后的图像
 */
vector<vector> floodFill(vector<vector>& img, int sr, int sc, int newColor) {

    // 关键优化：如果起始像素颜色已经是目标颜色，
    // 直接返回原图。这避免了不必要的递归调用和潜在的死循环。
    if (img[sr] == newColor) {
        return img;
    }

    // 提取原始颜色并开始 DFS 遍历
    int oldColor = img[sr];
    dfs(img, sr, sc, oldColor, newColor);

    return img;
}

//Driver Code Starts
int main() {
    vector<vector> img = {
        {1, 1, 1, 0},
        {0, 1, 1, 1},
        {1, 0, 1, 1}
    };

    int sr = 1, sc = 2;
    int newColor = 2;        

    vector<vector> result = floodFill(img, sr, sc, newColor);

    cout << "Flood Fill Result:" << endl;
    for (auto& row : result) {
        for (auto& pixel : row) {
            cout << pixel << " ";
        }
        cout << "
";
    }
    return 0;
}
//Driver Code Ends

代码实现 (Java):

//Driver Code Starts
class GFG {

//Driver Code Ends

    /**
     * Java DFS 实现
     */
    static void dfs(int[][] img, int x, int y, int oldColor, int newColor) {

        // 边界检查：确保 x, y 在图像范围内
        // 颜色检查：只处理颜色为 oldColor 的像素
        if (x = img.length ||
            y = img[0].length ||
            img[x][y] != oldColor) {

            return;
        }

        // 标记为已访问并更新颜色
        img[x][y] = newColor;

        // 递归遍历四个方向
        dfs(img, x + 1, y, oldColor, newColor);
        dfs(img, x - 1, y, oldColor, newColor);
        dfs(img, x, y + 1, oldColor, newColor);
        dfs(img, x, y - 1, oldColor, newColor);
    }

    static int[][] floodFill(int[][] img, int sr, int sc, int newColor) {
        
        // 防止 newColor 与 oldColor 相同导致无限递归
        if (img[sr] == newColor) {
            return img;
        }

        int oldColor = img[sr];
        dfs(img, sr, sc, oldColor, newColor);
        
        return img;
    }
    
    //Driver Code Starts
    public static void main(String[] args) {
        int[][] img = {
            {1, 1, 1, 0},
            {0, 1, 1, 1},
            {1, 0, 1, 1}
        };
        int sr = 1, sc = 2, newColor = 2;
        
        int[][] result = floodFill(img, sr, sc, newColor);
        
        System.out.println("Flood Fill Result:");
        for (int[] row : result) {
            for (int pixel : row) {
                System.out.print(pixel + " ");
            }
            System.out.println();
        }
    }
}
//Driver Code Ends

[方法 2] 使用广度优先搜索 – O(m n) 时间和 O(m n) 辅助空间

虽然 DFS 代码简洁，但在某些情况下，它可能会导致调用栈过深。这时，我们可以使用广度优先搜索（BFS）。BFS 使用队列来逐层处理像素，这在处理大面积填充时通常比递归 DFS 更稳定，因为它避免了栈溢出的风险。

代码实现 (C++):

#include 
#include 
using namespace std;

vector<vector> floodFillBFS(vector<vector>& img, int sr, int sc, int newColor) {
    if (img[sr] == newColor) return img;
    
    int oldColor = img[sr];
    int m = img.size();
    int n = img[0].size();
    
    // 使用队列存储待处理的坐标
    queue<pair> q;
    q.push({sr, sc});
    img[sr] = newColor; // 立即标记颜色
    
    // 方向数组：上、下、左、右
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        int x = p.first;
        int y = p.second;
        
        for (int i = 0; i = 0 && nx = 0 && ny < n && img[nx][ny] == oldColor) {
                img[nx][ny] = newColor;
                q.push({nx, ny});
            }
        }
    }
    return img;
}

深入生产环境：2026年视角下的挑战与对策

在我们掌握了基础算法后，让我们思考一下在真实的、大规模的生产环境中会发生什么。在我们的最近的一个云原生图像处理服务中，我们发现简单的 DFS/BFS 并不能解决所有问题。以下是我们在 2026 年的技术栈中应用的高级策略。

#### 1. 避免栈溢出：从递归到迭代

如果你在处理 4K 分辨率的图像，一个简单的递归 DFS 可能会导致调用栈过深，从而引发 Stack Overflow 错误。虽然 Java 的 JVM 可以配置栈大小，但在受限的容器环境（如 Docker 或 Kubernetes Pod）中，这并不是最佳实践。

最佳实践： 优先使用基于栈的迭代 DFS 或 BFS。这样我们可以使用堆内存，其大小通常远大于栈内存。

#### 2. 性能优化的终极手段：扫描线填充算法

你可能已经注意到，上述算法在检查每个像素的四个方向时，会进行大量的重复检查。对于现代图像处理，我们需要更高效的算法。扫描线填充算法 是工业界的首选。

原理：

不同于逐个像素填充，扫描线算法尝试填充整条水平线（扫描线）。当它找到一条需要填充的线段时，它会一次性填充整段，然后仅检查该线段上方和下方的相邻像素，以发现新的线段。

优势：

这种算法极大地减少了算法将像素入栈或入队的次数，大大提高了内存访问的局部性，从而利用 CPU 缓存加速计算。

// 扫描线填充伪代码逻辑
// 为了演示核心逻辑，这里使用简化的伪代码
void floodFillScanline(vector<vector>& img, int x, int y, int newColor) {
    int oldColor = img[x][y];
    if (oldColor == newColor) return;
    
    stack<pair> s;
    s.push({x, y});
    
    while(!s.empty()) {
        auto p = s.top(); s.pop();
        int cx = p.first, cy = p.second;
        
        // 1. 向右填充直到边界或不同颜色
        int y1 = cy;
        while (y1 >= 0 && img[cx][y1] == oldColor) img[cx][y1--] = newColor;
        y1++;
        
        // 2. 向左填充
        int y2 = cy + 1;
        while (y2 < img[0].size() && img[cx][y2] == oldColor) img[cx][y2++] = newColor;
        y2--;
        
        // 3. 检查上方和下方区间 (y1 到 y2)
        // 这里需要添加逻辑来检查 (cx-1) 和 (cx+1) 行在 [y1, y2] 范围内的像素
        // 并将新区间的端点压入栈中
        // ... (具体实现略繁琐，但核心在于利用线的连续性)
    }
}

#### 3. 结合 AI 辅助调试

在开发复杂算法时，我们如何验证其正确性？在 2026 年，我们不再依赖单纯的人工代码审查。我们使用 AI IDE（如 Cursor 或 Windsurf）来辅助。

场景： 假设我们实现的扫描线算法有一个微妙的边界检查 bug。

• 单元测试生成：我们首先让 AI 生成针对极端情况（如单一像素、全同色图像、棋盘格图像）的单元测试。
• 可视化调试：我们将网格数据输入给 AI 代理，让它生成填充前后的热力图或 ASCII 图，直观地展示算法的扩散路径。
• 代码修正：如果测试失败，AI 可以分析栈追踪，并指出我们在处理边缘像素时的逻辑漏洞（例如：未处理 INLINECODE18f62e4b 和 INLINECODE15a60b30 越界的情况）。

#### 4. 边界情况与容灾设计

在生产环境中，我们还需要考虑以下边界情况：

• 并发修改：如果两个线程同时尝试填充同一个图像的不同区域，该怎么办？我们需要使用读写锁或原子操作来保护图像数据。
• 内存限制：对于超大图像（如卫星地图），我们可能无法将整个 img 加载到内存。这时需要分块加载算法，结合磁盘缓冲区进行处理。

总结

Flood Fill 算法虽然概念简单，但在现代工程实践中，它的实现需要兼顾性能、稳定性和可维护性。从最初的 DFS 递归，为了防止栈溢出而进化为 BFS 或迭代 DFS，再到为了极致性能而采用的扫描线算法，每一步演进都是为了解决特定的工程痛点。

随着我们进入 2026 年，结合 AI 辅助的开发流程和强大的计算能力，我们不仅能更快地实现这些算法，还能以前所未有的可视化和自动化手段来保证代码质量。希望这篇文章能帮助你从更深层次理解这一经典算法，并在你的项目中灵活运用这些现代开发理念。