Learn how to implement the Floodfill algorithm - a powerful graph traversal technique used in image processing, game development, and more.
def flood_fill(grid, row, col, new_color, old_color=None):
if old_color is None:
old_color = grid[row][col]
# Check bounds and color match
if (row < 0 or row >= len(grid) or
col < 0 or col >= len(grid[0]) or
grid[row][col] != old_color):
return
# Fill current cell
grid[row][col] = new_color
# Recursively fill neighbors (4-way connectivity)
flood_fill(grid, row + 1, col, new_color, old_color) # Down
flood_fill(grid, row - 1, col, new_color, old_color) # Up
flood_fill(grid, row, col + 1, new_color, old_color) # Right
flood_fill(grid, row, col - 1, new_color, old_color) # Left
grid = [
[1, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 0, 0, 1],
[1, 1, 1, 1, 1]
]
# Fill starting at [1,1] with color 2
flood_fill(grid, 1, 1, 2)
print(grid)
# Output:
# [
# [1, 1, 1, 1, 1],
# [1, 2, 2, 2, 1],
# [1, 2, 2, 2, 1],
# [1, 1, 1, 1, 1]
# ]
def flood_fill_bfs(grid, row, col, new_color):
old_color = grid[row][col]
if old_color == new_color:
return grid # No need to fill if same color
queue = [[row, col]]
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] # Down, Up, Right, Left
while queue:
r, c = queue.pop(0)
# Check if this cell needs filling
if (r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or
grid[r][c] != old_color):
continue
# Fill current cell
grid[r][c] = new_color
# Add all adjacent cells to queue
for dr, dc in directions:
queue.append([r + dr, c + dc])
return grid
Implement a floodfill algorithm that uses 8-way connectivity (includes diagonals).
def flood_fill(grid, row, col, new_color, use_eight_way=False, old_color=None):
if old_color is None:
old_color = grid[row][col]
# Check bounds and color match
if (row < 0 or row >= len(grid) or
col < 0 or col >= len(grid[0]) or
grid[row][col] != old_color):
return
# Fill current cell
grid[row][col] = new_color
# Directions for 4-way connectivity
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
# Add diagonals for 8-way connectivity if needed
if use_eight_way:
directions += [[1, 1], [1, -1], [-1, 1], [-1, -1]]
for dr, dc in directions:
flood_fill(grid, row + dr, col + dc, new_color, use_eight_way, old_color)
# Create a test grid
grid1 = [
[1, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 0, 0, 1],
[1, 1, 1, 1, 1]
]
# Test with 4-way connectivity
grid2 = [row[:] for row in grid1] # Deep copy
flood_fill(grid2, 1, 1, 2, False)
print("4-way result:")
print(grid2)
# Test with 8-way connectivity
grid3 = [row[:] for row in grid1] # Deep copy
flood_fill(grid3, 1, 1, 2, True)
print("8-way result:")
print(grid3)
After completing this challenge, try these LeetCode problems: