洪水填充算法与 DFS/BFS 应用总结

floodfill 算法

1. 寻找相同性质的连通块，可以使用 DFS 或者 BFS 解决，比如把 1 连通块的周围都修改为 2

图像渲染

题目链接

题解

1. 我们通过将以 sr，sc 为起始点，将该点周围的连通块都修改为 color
2. 全局变量：p 记录要修改的连通块的值，m，n 矩阵的长和宽，坐标 dx，dy 向上下左右方向搜索
3. 细节处理：如果起始点（sr，sc）就是 color 的值，不需要修改直接返回矩阵，因为该点周围已经被渲染为 color 颜色了，这样会无限渲染下去，因为是同一个值，未改变，具体可以看实例二

代码

class Solution {
public:
    int m, n;
    int p; // 渲染一个连通块
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        p = image[sr][sc];
        m = image.size(), n = image[0].size();
        // 避免死循环，该点和该点周围一圈都是目标颜色，就无限进入循环中
        if (image[sr][sc] == color) return image;
        dfs(image, sr, sc, color);
        return image;
    }
     dx[] = {, , , };
     dy[] = {, , , };
    {
        image[i][j] = color;
         ( k = ; k < ; k++) {
            
             x = dx[k] + i, y = dy[k] + j;
             (x >=  && x < m && y >=  && y < n && image[x][y] == p) {
                (image, x, y, color);
            }
        }
    }
};