This is the third day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

The title

A drawing is presented as a two-dimensional array of integers, each integer representing the pixel value of the drawing, ranging from 0 to 65535.

You are given a coordinate (sr, sc) representing the pixel value (row, column) at the beginning of the image rendering and a newColor value, newColor, to recolor the image.

In order to complete the coloring work, starting from the initial coordinates, record the connected pixels with the same pixel value in the four directions of the initial coordinates, and then record the qualified pixels in these four directions and their corresponding connected pixels with the same pixel value in the four directions of the initial coordinates… And repeat the process. Change the color value of all recorded pixels to the new color value.

Finally, the color rendered image is returned.

The sample

Input: image = [,1,1 [1], [1, 0], [1, 1]] sr = 1, sc = 1, newColor = 2 output: [,2,2 [2], [2 0], [2, 1]] resolution: In the middle of the image, (coordinates (sr,sc)=(1,1)), the color of all eligible pixels on the path is changed to 2. Notice that the lower-right pixel is not changed to 2 because it is not the pixel that is connected to the initial point in four directions: up, down, left, and right.Copy the code

prompt

  • image 和 image[0]The length is in the range50] [1,Inside.
  • The initial points given will satisfy0 <= sr < image.length 和 0 <= sc < image[0].length.
  • image[i][j] 和 newColorRepresents a color value in the range[0, 65535]Inside.

Their thinking

Depth-first search

For the pixel at the given coordinate [sr, sc], we need to compare it with the newColor value newColor first. Only when the two are different, the significance of replacement can be obtained.

Then, starting at the coordinate point [SR, sc], spread the render around (up/down/left/right) until the pixel value is not equal to the original pixel at [sr, sc].

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        // If you want to replace the color with the new color, return it directly
        if(image[sr][sc] ! = newColor){// The color is inconsistent
            fill(image, sr, sc, image[sr][sc], newColor);
        }
        // Return the result
        return image;
    }

    /** ** replace *@paramImage Image array *@paramSr x star@paramSc y star@paramOldColor needs to be replaced by *@paramNewColor newColor */
    public void fill(int[][] image, int sr, int sc, int oldColor, int newColor){
        // boundary judgment
        if(sr < 0 || sr == image.length || sc < 0 || sc == image[0].length || image[sr][sc] ! = oldColor){return;
        }
        // Change the color
        image[sr][sc] = newColor;
        // Search left for substitution
        fill(image, sr + 1, sc, oldColor, newColor);
        // Search right for substitution
        fill(image, sr, sc + 1, oldColor, newColor);
        // Search up for replacement
        fill(image, sr - 1, sc, oldColor, newColor);
        // Search down for replacements
        fill(image, sr, sc - 1, oldColor, newColor); }}Copy the code

Complexity analysis

  • O(NM)O(NM)O(NM)
  • Space complexity: O(NM)O(NM)O(NM)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/fl…