Given an image represented as a 2D grid, a starting pixel (sr, sc), and a new color, fill all connected pixels that share the same original color as the starting pixel with the new color. Use recursive depth-first search to visit all 4-directionally adjacent pixels.
Same flood fill logic but uses an iterative breadth-first search with a queue instead of recursion. This avoids potential stack overflow on very large images.
""" 0733.1 - Flood Fill - Solution 1 - Recursive DFS """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
"""Flood Fill Function"""
original = image[sr][sc]
if original == color:
return image
rows, cols = len(image), len(image[0])
def dfs(r: int, c: int) -> None:
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if image[r][c] != original:
return
image[r][c] = color
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
dfs(sr, sc)
return image
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2))
# Expected: [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
print(Solution().floodFill([[0, 0, 0], [0, 0, 0]], 0, 0, 0))
# Expected: [[0, 0, 0], [0, 0, 0]]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0733.2 - Flood Fill - Solution 2 - Iterative BFS """
#####################################################################################
# Imports
#####################################################################################
from typing import List
from collections import deque
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
"""Flood Fill Function"""
original = image[sr][sc]
if original == color:
return image
rows, cols = len(image), len(image[0])
queue = deque([(sr, sc)])
image[sr][sc] = color
while queue:
r, c = queue.popleft()
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original:
image[nr][nc] = color
queue.append((nr, nc))
return image
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2))
# Expected: [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
print(Solution().floodFill([[0, 0, 0], [0, 0, 0]], 0, 0, 0))
# Expected: [[0, 0, 0], [0, 0, 0]]
#####################################################################################
# Functions
#####################################################################################
if __name__ == "__main__":
testcase()