LeetCode – Flood Fill

题目：

Input: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: 
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected 
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.

解题：

      算法遍历所有的节点以寻找和起始节点相连的节点（通过一条目标颜色的路径相连），然后 改变他们的颜色为替换颜色。目前有许多flood-fill算法的构建方式，算法分为四路算法（不考虑对角线方向的节点）和八路算法（考虑对角线方向的节点）。下面是个四路算法实现：

     递归方式DFS：

      首先判断如果给定位置的颜色跟新的颜色相同的话，直接返回，否则就对给定位置调用递归函数。在递归函数中，如果越界或者当前颜色跟起始颜色不同，直接返回。否则当前位置设置新颜色，然后对上下左右四个方向继续调用递归函数，参见代码如下：

实现：

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        if (image[sr][sc] == newColor) return image;
        fill(image, sr, sc, image[sr][sc], newColor);
        return image;
        
    }
    
    void fill(vector<vector<int>>& image, int sr, int sc,int color, int newColor) {
        if (sr<0 ||sr>=image.size() || sc<0 || sc>=image[0].size()|| color != image[sr][sc]) return ;
        image[sr][sc] = newColor;
        fill(image, sr, sc-1, color, newColor);
        fill(image, sr, sc+1, color, newColor);
        fill(image, sr-1, sc, color, newColor);
        fill(image, sr+1, sc, color, newColor);
        
    }
};
/*
 1. If target-color is equal to replacement-color, return.
 2. ElseIf the color of node is not equal to target-color, return.
 3. Else Set the color of node to replacement-color.
 4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
 5. Return.
 */

解题：

     借助队列 BFS：

     首先将给定点放入队列中，然后进行while循环，条件是queue不为空，然后进行类似层序遍历的方法，取出队首元素，将其赋值为新的颜色，然后遍历周围四个点，如果不越界，且周围的颜色跟起始颜色相同的话，将位置加入队列中，参见代码如下：

实现：  

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    queue<pair<int,int>> q;
    q.push({sr,sc});
    int colour = image[sr][sc];
    vector<pair<int,int>> dirs = {{0,1},{1,0}, {-1,0}, {0,-1}, {0,0}};
    
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(auto it: dirs)
        {
            int r = it.first + x;
            int c = it.second + y;
   if(r<0 || c<0 || r>= image.size() || c>= image[0].size() || image[r][c] == newColor || image[r][c]!=colour)
                continue;
            
            image[r][c] = newColor;
            q.push({r,c});
            
        }
    }
    
    return image;
    }
};

参考引用：

C++-clean-BFS-solution-(Beats-98)

Java-9-liner-DFS

[LeetCode] Flood Fill 洪水填充