How do you solve the flood fill problem, and what is the subtlety?
You change the colour of the starting pixel and then you spread out to the four neighbours of every pixel you change, as long as they have the original colour.
def flood_fill(image, sr, sc, color):
if not image or not image[0]:
return image
rows, cols = len(image), len(image[0])
original = image[sr][sc]
if original == color:
return image
def fill(row, col):
if row < 0 or row >= rows or col < 0 or col >= cols:
return
if image[row][col] != original:
return
image[row][col] = color
fill(row - 1, col)
fill(row + 1, col)
fill(row, col - 1)
fill(row, col + 1)
fill(sr, sc)
return image
And what is the subtlety? There are two of them.
The first one is that you have to remember the original colour. If you change the colour of a pixel and then look at its neighbours, the neighbour check has to compare against the colour that the region started with, and not against the new colour. So the code saves the original colour in a variable before anything changes.
The second one is that the check has to come before the change. If the pixel already has the new colour then the fill would spread out over the whole new colour region, which is not what was asked. And if the original colour is the same as the new colour then nothing should happen at all, so the function returns straight away.
the image
[[1, 1, 0],
[1, 1, 0],
[0, 0, 0]]
filling from (0, 0) with the colour 2
the answer
[[2, 2, 0],
[2, 2, 0],
[0, 0, 0]]
And the complexity is O of rows times columns for the time, because every pixel in the region is changed once, and O of h for the space of the call stack, where h is the height of the region.
So the rule to remember is this. Save the original colour first, and compare against it every time.
The next two questions in this topic show the queue version and the region counting version.