LeetCode – Flood Fill

题目:

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.

To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

Example 1:

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.

Note:

  • The length of image and image[0] will be in the range [1, 50].
  • The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.
  • The value of each color in image[i][j] and newColor will be an integer in [0, 65535].
   Hide Hint #1  
 
Write a recursive function that paints the pixel if it's the correct color, then recurses on neighboring pixels.

 

解题:

      算法遍历所有的节点以寻找和起始节点相连的节点(通过一条目标颜色的路径相连),然后 改变他们的颜色为替换颜色。目前有许多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 洪水填充

 

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注