“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