“This is the 14th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

describe

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and newColor. You should perform a flood fill on the image starting from the pixel image[sr][sc].

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), and so on. Replace the color of all of the aforementioned pixels with newColor.

Return the modified image after performing the flood fill.

Example 1:

,1,1 Input: image = [[1], [1, 0], [1, 1]], the sr = 1, sc = 1, the Output newColor = 2: [,2,2 [2], [2 0], [2, 1]] Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) 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.Copy the code

Example 2:

Input: image = [[0, 0], [0, 0]], the sr = 0, sc = 0, newColor = 2 Output: [,2,2 [2], [2,2,2]]Copy the code

Note:

m == image.length
n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], newColor < 2^16
0 <= sr < m
0 <= sc < n
Copy the code

parsing

According to the meaning of the question, an MxN photo image is presented, and the value of image[I][j] represents pixel. Flood Fill is performed from image[sr][sc] of the photo.

In fact, flood fill operation is to replace the values of image[sr][SC] with newColor if the four adjacent positions of the position or the four adjacent positions of image[SR][SC] are the same. The idea is simple, similar to BFS:

  • For initialization, M represents the number of rows, N represents the number of columns, visited represents the position of the last value to be converted, oldColor records the pixel of the starting position, and stack is used to record all the effective positions, up, down and left
  • Through the position in the stack, pop up the first position of the stack, add it to the visited, then find the effective position in the four adjacent directions of the position, and continue the cycle of traversal
  • Finally, we will go through all the locations in visited, replace the old values in these locations with newColor, and finally return image

answer

class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        """
        M = len(image)
        N = len(image[0])
        stack = [[sr, sc]]
        visited = []
        oldColor = image[sr][sc]
        while stack:
            x, y = stack.pop(0)
            visited.append([x, y])
            if x + 1 < M and image[x + 1][y] == oldColor:
                if [x + 1, y] not in visited:
                    stack.append([x + 1, y])
            if x - 1 > -1 and image[x - 1][y] == oldColor:
                if [x - 1, y] not in visited:
                    stack.append([x - 1, y])
            if y - 1 > -1 and image[x][y - 1] == oldColor:
                if [x, y - 1] not in visited:
                    stack.append([x, y - 1])
            if y + 1 < N and image[x][y + 1] == oldColor:
                if [x, y + 1] not in visited:
                    stack.append([x, y + 1])
        for x, y in visited:
            image[x][y] = newColor
        return image
        	      
		
Copy the code

The results

Given the submission in the Python online list for Flood Fill. Memory Usage: Submissions in Python online submission for Flood Fill.Copy the code

parsing

Of course, you can also use DFS to solve the problem, and the principle is similar. The result is not as good as BFS.

answer

class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        """
        M = len(image)
        N = len(image[0])
        oldColor = image[sr][sc]
        if oldColor == newColor:return image
        def dfs(x, y):
            if image[x][y] == oldColor:
                image[x][y] = newColor
                if x-1 > -1: dfs(x-1, y)
                if x+1 < M: dfs(x+1, y)
                if y-1 > -1: dfs(x, y-1)
                if y+1 < N: dfs(x, y+1)
        dfs(sr, sc)
        return image			
Copy the code

The results

Given in the Python online submission for Flood Fill. Memory Usage: Submissions in Python online submissions for Flood Fill.Copy the code

Original link: leetcode.com/problems/fl…

Your support is my biggest motivation