What is the Flood Fill algorithm?

The Flood Fill algorithm is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is often used in image processing and games to fill a connected region with a specific color.

How can Flood Fill be implemented?

Flood Fill can be implemented using graph traversal algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS). A recursive DFS approach is often the most straightforward way to implement it.

Graph Traversal

Flood Fill Algorithm

A fundamental algorithm for visiting connected components in a grid, often visualized as 'coloring' a region, with applications in image editing and puzzle games.

Flood Fill in Python (DFS)

Here is a Python implementation of the Flood Fill algorithm using a recursive Depth-First Search (DFS) approach.

def flood_fill(image, sr, sc, new_color):
    rows, cols = len(image), len(image[0])
    original_color = image[sr][sc]
    if original_color == new_color:
        return image

    def dfs(r, c):
        if (r < 0 or r >= rows or c < 0 or c >= cols or
                image[r][c] != original_color):
            return

        image[r][c] = new_color
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    dfs(sr, sc)
    return image

AI Coach Hint: The recursive DFS implementation of Flood Fill is elegant but can lead to a stack overflow on very large areas. For production systems, an iterative BFS approach using a queue is often preferred for its stability.