Implement BFS and DFS on GridsStep 2 of 5

Flood fill

12345

Step 2: Flood fill

This is the paint-bucket tool. Starting from one cell, recolor every cell in its connected same-color region.

Write flood_fill(grid, sr, sc, new_color) that:

  1. Reads the start color at (sr, sc).
  2. Replaces that color with new_color for every cell reachable from the start through 4-directional moves over cells sharing the start color.
  3. Returns the (mutated) grid.

If the start color already equals new_color, return the grid unchanged. Otherwise you would loop forever. Reuse neighbors from Step 1 to walk the region with a DFS stack.

Hints
Starter code
def neighbors(grid, r, c):
    """Return in-bounds 4-directional neighbor coords: up, down, left, right."""
    rows = len(grid)
    cols = len(grid[0]) if rows else 0
    result = []
    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
        if 0 <= nr < rows and 0 <= nc < cols:
            result.append((nr, nc))
    return result


def flood_fill(grid, sr, sc, new_color):
    """Fill the connected region of the start cell's color with new_color."""
    # TODO: DFS from (sr, sc), recoloring cells that match the start color
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step