Seed fill use case.
In Computer Sciense a Flood fill or a Seed fill is a flooding technique that determines and alters the area connected to a given node in a multi-dimensional array with some matching attribute. It is practical use case is a "bucket" fill tool of paint programs to paint connected similarly-colored areas with a new color. So graphical tools and game industry are the main users of Flood fill algorithm.
The algorithm defines all nodes in the array that are connected to the start node by the target color and changes them to the new replacement color.
Flood fill Algorithm Python code:
# Screen Dimensions
M = 8
N = 8
screen = [[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 0, 0],
[1, 0, 0, 1, 1, 0, 1, 1],
[1, 0, 2, 2, 2, 0, 1, 0],
[1, 1, 2, 2, 2, 0, 1, 0],
[1, 1, 2, 2, 2, 2, 1, 0],
[1, 1, 1, 1, 1, 2, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1]]
x = 4
y = 4
newColor = 5
# A recursive replacement function
def floodFillUtil(screen, x, y, prevColor, newColor):
if (x < 0 or x >= M or y < 0 or
y >= N or screen[x][y] != prevColor or
screen[x][y] == newColor):
return
screen[x][y] = newColor
# Recursioin in every direction
floodFillUtil(screen, x + 1, y, prevColor, newColor)
floodFillUtil(screen, x - 1, y, prevColor, newColor)
floodFillUtil(screen, x, y + 1, prevColor, newColor)
floodFillUtil(screen, x, y - 1, prevColor, newColor)
# finds the previous color on and calls replacement function
def FloodFill(screen, x, y, newColor):
prevColor = screen[x][y]
if(prevColor==newColor):
return
floodFillUtil(screen, x, y, prevColor, newColor)
FloodFill(screen, x, y, newColor)
print ("Flood Fill output :\n")
for i in range(M):
for j in range(N):
print(screen[i][j], end = ' ')
print()
