135. Surrounded Regions

Why this mechanism works

It is easier to prove which cells must survive than to examine every enclosed region independently. Start from all border O cells and mark their reachable region temporarily. Every remaining O is enclosed; after flipping those cells, restore the temporary marks.

State and boundaries

Temporary 'S' marks O cells connected to a border. queue contains discovered safe cells awaiting expansion.

Protocol

1. Mark and enqueue all border O cells.
2. Flood through four-neighbor O cells, marking on discovery.
3. Scan the board.
4. Convert unmarked O to X and S back to O.

Visualization

border O -> mark all reachable O as S
remaining O has no border path -> X
restore S -> O

Python implementation

from collections import deque

def surrounded_regions(board):
    if not board or not board[0]:
        return board
    rows, cols = len(board), len(board[0])
    queue = deque()
    def mark(r, c):
        if 0 <= r < rows and 0 <= c < cols and board[r][c] == 'O':
            board[r][c] = 'S'
            queue.append((r, c))
    for r in range(rows):
        mark(r, 0)
        mark(r, cols - 1)
    for c in range(cols):
        mark(0, c)
        mark(rows - 1, c)
    while queue:
        r, c = queue.popleft()
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            mark(r + dr, c + dc)
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 'O':
                board[r][c] = 'X'
            elif board[r][c] == 'S':
                board[r][c] = 'O'
    return board

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 surrounded_regions: if not board or not board[0]:
board=[['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']]

L6 surrounded_regions: rows, cols = len(board), len(board[0])
board=[['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']]; cols=4; rows=4

L7 surrounded_regions: queue = deque()
board=[['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']]; cols=4; rows=4; queue=deque([])

L12 surrounded_regions: for r in range(rows):
board=[['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']]; cols=4; rows=4; queue=deque([]); r=0

L9 mark: if 0 <= r < rows and 0 <= c < cols and board[r][c] == 'O':
r=0; c=0; board=[['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']]; cols=4; queue=deque([]); rows=4

L9 mark: if 0 <= r < rows and 0 <= c < cols and board[r][c] == 'O':
r=0; c=3; board=[['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']]; cols=4; queue=deque([]); rows=4

L12 surrounded_regions: for r in range(rows):
board=[['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']]; cols=4; rows=4; queue=deque([]); r=1

L9 mark: if 0 <= r < rows and 0 <= c < cols and board[r][c] == 'O':
r=1; c=0; board=[['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']]; cols=4; queue=deque([]); rows=4

... 51 intermediate state changes omitted ...

L23 surrounded_regions: for c in range(cols):
board=[['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'S', 'X', 'X']]; cols=4; rows=4; queue=deque([]); r=3; c=1; dr=0; dc=-1

L27 surrounded_regions: board[r][c] = 'O'
board=[['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'X']]; cols=4; rows=4; queue=deque([]); r=3; c=1; dr=0; dc=-1

L23 surrounded_regions: for c in range(cols):
board=[['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'X']]; cols=4; rows=4; queue=deque([]); r=3; c=2; dr=0; dc=-1

L23 surrounded_regions: for c in range(cols):
board=[['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'X']]; cols=4; rows=4; queue=deque([]); r=3; c=3; dr=0; dc=-1

L4 surrounded_regions: if not board or not board[0]:
board=[['O', 'O']]

L6 surrounded_regions: rows, cols = len(board), len(board[0])
board=[['O', 'O']]; cols=2; rows=1

L7 surrounded_regions: queue = deque()
board=[['O', 'O']]; cols=2; rows=1; queue=deque([])

L12 surrounded_regions: for r in range(rows):
board=[['O', 'O']]; cols=2; rows=1; queue=deque([]); r=0

L9 mark: if 0 <= r < rows and 0 <= c < cols and board[r][c] == 'O':
r=0; c=0; board=[['O', 'O']]; cols=2; queue=deque([]); rows=1

L10 mark: board[r][c] = 'S'
r=0; c=0; board=[['S', 'O']]; cols=2; queue=deque([]); rows=1

L11 mark: queue.append((r, c))
r=0; c=0; board=[['S', 'O']]; cols=2; queue=deque([(0, 0)]); rows=1

L13 surrounded_regions: mark(r, 0)
board=[['S', 'O']]; cols=2; rows=1; queue=deque([(0, 0)]); r=0

... 28 intermediate state changes omitted ...

L23 surrounded_regions: for c in range(cols):
board=[['S', 'S']]; cols=2; rows=1; queue=deque([]); r=0; c=0; dr=0; dc=-1

L27 surrounded_regions: board[r][c] = 'O'
board=[['O', 'S']]; cols=2; rows=1; queue=deque([]); r=0; c=0; dr=0; dc=-1

L23 surrounded_regions: for c in range(cols):
board=[['O', 'S']]; cols=2; rows=1; queue=deque([]); r=0; c=1; dr=0; dc=-1

L27 surrounded_regions: board[r][c] = 'O'
board=[['O', 'O']]; cols=2; rows=1; queue=deque([]); r=0; c=1; dr=0; dc=-1

Why the solution is correct

A marked cell has an O-only path to a border, so it must survive. Every border-connected O is reachable from one of the seeded cells and is marked. Consequently the unmarked O cells are exactly the regions with no border path, which the contract requires flipping.

Time and space

O(R*C) time and O(R*C) queue space; temporary marks reuse the board.

Common mistakes

Starting only from corners misses other border connections. Restoring marks before the final classification loses the safe/enclosed distinction.

Reasoning card

Transfer exercise

Model an outside super-node and solve the same preservation question with union-find.