Given a m x n integer grid image and integers sr, sc, and newColor, write a function to perform a flood fill on the image starting from the pixel image[sr][sc].
In a 'flood fill', start by changing the color of image[sr][sc] to newColor. Then, change the color of all pixels connected to image[sr][sc] from either the top, bottom, left or right that have the same color as image[sr][sc], along with all the connected pixels of those pixels, and so on.
Input: image = [[1,0,1],[1,0,0],[0,0,1]], sr = 1, sc = 1, color = 2
Output: [[1,2,1],[1,2,2],[2,2,1]]
The zeroes connected to the starting pixel (1, 1) are colored with the new color (2).
Explanation
This solution uses depth-first search to traverse the grid and perform the flood fill by defining a recursive function dfs that takes in the current row and column of the pixel being explored. Each call to dfs will either change the color of the pixel if the pixel is the same color as the starting pixel, and then recursively call dfs on its connected pixels. If the pixel is not the same color as the starting pixel, the function will return without doing anything.
The algorithm starts at the given starting pixel and uses depth-first search to explore all pixels connected 4-directionally to it. At each pixel, it first checks to see if the pixel is the same color as the starting pixel. If it is, it changes the color of the pixel and continues to explore the connected pixels.
Python
defflood_fill(image, sr, sc, color):
rows, cols =len(image),len(image[0])
original_color = image[sr][sc]
if original_color == color:
return image
defdfs(r, c):
if image[r][c]== original_color:
image[r][c]= color
if r >=1: dfs(r -1, c)
if r +1< rows: dfs(r +1, c)
if c >=1: dfs(r, c -1)
if c +1< cols: dfs(r, c +1)
return
dfs(sr, sc)
return image
defdfs(r, c):
if image[r][c]== original_color:
image[r][c]= color
if r >=1: dfs(r -1, c)
if r +1< rows: dfs(r +1, c)
if c >=1: dfs(r, c -1)
if c +1< cols: dfs(r, c +1)
return
update color
0 / 2
1x
Setting the color of connected pixels.
After changing that pixel's color, the algorithm will continue to explore the connected pixels of that pixel. Whenever it encounters a pixel that is not the same color as the starting pixel, it will return immediately and backtrack to the previous pixel on the call stack, which will then continue to explore its remaining connected pixels.
Python
defflood_fill(image, sr, sc, color):
rows, cols =len(image),len(image[0])
original_color = image[sr][sc]
if original_color == color:
return image
defdfs(r, c):
if image[r][c]== original_color:
image[r][c]= color
if r >=1: dfs(r -1, c)
if r +1< rows: dfs(r +1, c)
if c >=1: dfs(r, c -1)
if c +1< cols: dfs(r, c +1)
return
dfs(sr, sc)
return image
defdfs(r, c):
if image[r][c]== original_color:
image[r][c]= color
if r >=1: dfs(r -1, c)
if r +1< rows: dfs(r +1, c)
if c >=1: dfs(r, c -1)
if c +1< cols: dfs(r, c +1)
return
defdfs(r, c):
if image[r][c]== original_color:
image[r][c]= color
if r >=1: dfs(r -1, c)
if r +1< rows: dfs(r +1, c)
if c >=1: dfs(r, c -1)
if c +1< cols: dfs(r, c +1)
return
defdfs(r, c):
if image[r][c]== original_color:
image[r][c]= color
if r >=1: dfs(r -1, c)
if r +1< rows: dfs(r +1, c)
if c >=1: dfs(r, c -1)
if c +1< cols: dfs(r, c +1)
return
recursive call
0 / 6
1x
Backtracking to the previous pixel
The algorithm will continue to explore the connected pixels of the starting pixel until it has explored all connected pixels of the start pixel. The time complexity of this algorithm is O(n * m) where n is the number of rows and m is the number of columns in the grid.
Your account is free and you can post anonymously if you choose.