Fill in the water that does not touch the edge

Flip the question: find the water that does touch the edge. Search from every edge water cell and mark what it reaches. Everything else that is water must be enclosed, so turn it into land. O(R·C) time and space.

Searching from the border is the same 'start from the boundary' trick as the two-coasts problem.

Checking each region for an edge cell as you flood it also works; the border-first version is simpler.

Returning a new list of strings avoids mutating the caller's data.

STEPS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def fill_enclosed(grid: list[str]) -> list[str]:
    rows, cols = len(grid), len(grid[0]) if grid else 0
    todo = [(r, c) for r, row in enumerate(grid)
            for c, ch in enumerate(row)
            if ch == "."
            and not (0 < r < rows - 1 and 0 < c < cols - 1)]
    escapes = set(todo)
    while todo:
        y, x = todo.pop()
        for dy, dx in STEPS:
            ny, nx = y + dy, x + dx
            inside = 0 <= ny < rows and 0 <= nx < cols
            if (inside and grid[ny][nx] == "."
                    and (ny, nx) not in escapes):
                escapes.add((ny, nx))
                todo.append((ny, nx))
    return ["".join("." if (r, c) in escapes else "#"
                    for c in range(len(row)))
            for r, row in enumerate(grid)]

Common mistakes

• Counting diagonal contact with edge water as an escape when the question uses four directions.
• Treating a water cell that sits on the edge as enclosed.

Explain the flip: mark what escapes, fill the rest.

Follow-up questions

Think of your answer first, then open the hint.

1. How would you count enclosed regions instead?

   Show hint

   Flood each interior water region and count those that never reach the edge.

2. What if the map wraps around?

   Show hint

   Then there is no edge, and every region is enclosed unless defined otherwise.