Surrounded Regions

Surrounded Regions is a classic grid problem. It looks like it wants you to find captured regions directly — but the clean trick is to flip the question around and find the cells that cannot be captured first.

The slow way first

You might try to scan each region of O and ask 'does this region touch the border?' But finding regions, tracking which ones reach an edge, and then deciding what to flip is fiddly and easy to get wrong. You end up doing the same flood fill but with bookkeeping bolted on.

The question to ask: which O cells are definitely safe? An O survives only if it is connected to the border. That set is much easier to compute directly — and everything else is captured by definition.

The idea: mark the survivors, capture the rest

Run a DFS starting from every O on the border. Each cell that flood reaches is safe — temporarily mark it "S". After all border floods finish, walk the whole grid once: any cell still "O" was never reached, so it is surrounded — flip it to "X". Turn every "S" back into "O".

The key insight: it is far easier to find the cells that are safe than the cells that are surrounded. Compute the safe set, and the surrounded set is simply 'everything else'.

Walk through it

Step through the animation. We scan the border, find the one O on the right edge, and DFS-flood from it — each reached O turns green (safe). Then we sweep the grid: any O that never turned green would flip to X. Here the whole region was border-connected, so all three cells survive.

Pseudocode

for every cell on the border that is "O":
    DFS flood from it, marking each reachable "O" as "S" (safe)
 
for every cell in the grid:
    if it is "S":  set it back to "O"   # survived
    else if "O":   set it to "X"        # surrounded, captured

The Python solution

def solve(board):
    rows, cols = len(board), len(board[0])
 
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if board[r][c] != "O":
            return
        board[r][c] = "S"          # mark safe
        dfs(r - 1, c); dfs(r + 1, c)
        dfs(r, c - 1); dfs(r, c + 1)
 
    for r in range(rows):
        for c in range(cols):
            border = r in (0, rows - 1) or c in (0, cols - 1)
            if border and board[r][c] == "O":
                dfs(r, c)
 
    for r in range(rows):
        for c in range(cols):
            board[r][c] = "O" if board[r][c] == "S" else "X"

• dfs floods from a cell, stopping at the grid edge or any non-O cell.
• Marking a reached cell as "S" doubles as the visited guard — dfs returns immediately on anything that is not "O", so an "S" cell is never revisited.
• The first double loop launches a flood from every border O. After it finishes, every "S" is a border-connected survivor.
• The second double loop is the capture sweep: "S" returns to "O", and any remaining "O" (never reached) becomes "X".

Complexity

Time is O(m·n) — every cell is touched a constant number of times. Space is O(m·n) in the worst case for the DFS recursion stack (a grid that is one big snake of O).

When this pattern shows up

Practice