Capture every region of O cells walled in by X. Flood fill from the border to mark the O cells that escape; the rest get captured.
▼The problem
LeetCode 130 (Medium). Given an m × n board of 'X' and 'O', capture every region of 'O' cells that is fully surrounded by 'X' (4-directionally): flip all of its cells to 'X', in place. A region with any cell on the border of the board is not surrounded and stays.
Example (LeetCode's): [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] → [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]: the three O cells in the middle flip; the O on the bottom edge survives.
The solution
def solve(board):
m, n = len(board), len(board[0])
def mark(r, c):
if 0 <= r < m and 0 <= c < n and board[r][c] == 'O':
board[r][c] = 'S'
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
mark(r + dr, c + dc)
for r in range(m):
for c in range(n):
if r in (0, m - 1) or c in (0, n - 1):
mark(r, c)
for r in range(m):
for c in range(n):
board[r][c] = 'O' if board[r][c] == 'S' else 'X'Transcript
Surrounded Regions. A board holds X walls and O camps. Any group of O cells sealed in by X on every side is captured, and flips to X. A group that touches the edge escapes.
On this four by four board, the three O cells in the middle are walled in, so they flip. The O on the bottom edge touches the border, so it stays.
The naive way: from every O, search outward to see if it reaches the edge. But cells in the same region repeat the same search: up to m times n searches, each touching m times n cells.
Better: flip the question. Don't ask who is trapped; ask who can escape. Every O that escapes is connected to an O on the border. So flood fill inward from each border O, and mark everything you reach as safe. Whatever is left is captured.
In code, walk the border, and run a depth-first mark from every O you find, turning it into S. Then sweep the board once: an O becomes X, and an S goes back to O.
Try a five by seven board. The border walk finds an O on the top edge, and the flood follows it down and left, four cells in all. Another O on the left edge marks two. Now sweep: the group of three and the lone O were never reached, so they flip. The six safe cells turn back into O.
Each cell is marked at most once and swept once: order m times n time. The recursion can hold every cell: order m times n space.
Start from the edge, mark who escapes, and capture the rest. That's Surrounded Regions.