from collections import deque
# flood‑fill an area in a matrix — starting from a given cell
# replacing all connected cells that have the same original value
# with a new value.
# same idea as the "paint bucket" tool in image editors.
# Given
# A matrix of 0s and 1s (or any numbers)
# A starting point (r, c)
# A new number to fill with
# Replace all connected cells (4‑directionally)
# that have the same value as the start cell.
def flood_fill(matrix, start_r, start_c, new_value):
# Number of rows and columns in the matrix
rows, cols = len(matrix), len(matrix[0])
# The value we want to replace (the value at the starting cell)
original_value = matrix[start_r][start_c]
# If the new value is the same as the original, nothing needs to change
if original_value == new_value:
return matrix
# Queue for BFS (queue-based); starts with the initial cell
queue = deque([(start_r, start_c)])
# Replace the starting cell with the new value
matrix[start_r][start_c] = new_value
# Directions for moving: down, up, right, left
# Each pair (dr, dc) represents a row and column offset
directions = [(1,0), (-1,0), (0,1), (0,-1)]
while queue:
# Current cell being processed
r, c = queue.popleft()
# Check all 4 neighboring cells
for dr, dc in directions:
nr, nc = r + dr, c + dc # New row and column
# Make sure the new position is inside the matrix
if 0 <= nr < rows and 0 <= nc < cols:
# Only fill cells that match the original value
if matrix[nr][nc] == original_value:
matrix[nr][nc] = new_value # Fill the cell
queue.append((nr, nc)) # Add it to the queue to continue filling
return matrix
matrix = [
[1, 1, 0, 0],
[1, 0, 0, 1],
[1, 1, 1, 1]
]
result = flood_fill(matrix, 0, 0, 9)
for row in result:
print(row)
'''
run:
[9, 9, 0, 0]
[9, 0, 0, 9]
[9, 9, 9, 9]
'''
