The problem
A board holds X and O. A region of Os (joined horizontally or vertically) is captured if it is completely surrounded by X — that is, if none of its cells is on the board’s edge. Capturing turns all its Os into X.
Capture every surrounded region, changing the board in place.
Examples
01
- Input
board = [ ["X", "X", "X", "X"], ["X", "O", "O", "X"], ["X", "X", "O", "X"], ["X", "O", "X", "X"] ]
- Output
[ ["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "O", "X", "X"] ]
02
- Input
board = [["X"]]
- Output
[["X"]]
Constraints
- 1 ≤ m, n ≤ 200
- Each cell is "X" or "O".
The idea
Finding each region and checking whether it touches the edge works, but the reverse is simpler: the regions that survive are exactly those joined to an O on the edge.
So start from every O on the border and spread through its region, marking the cells safe (S). Afterwards, every O still unmarked is surrounded — make it X — and every S goes back to O.
- Time
- O(m · n)
- Space
- O(m · n) — the stack
Solution · every language run against every case
class Solution: def solve(self, board: List[List[str]]) -> None: rows, cols = len(board), len(board[0]) # An O region survives exactly when it touches the edge. Mark those as safe ("S") # by spreading from every O on the edge. stack = [(r, c) for r in range(rows) for c in range(cols) if (r in (0, rows - 1) or c in (0, cols - 1)) and board[r][c] == "O"] for r, c in stack: board[r][c] = "S" while stack: i, j = stack.pop() for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)): if 0 <= x < rows and 0 <= y < cols and board[x][y] == "O": board[x][y] = "S" stack.append((x, y)) # Every O left is surrounded: capture it. Then the safe ones go back to O. for r in range(rows): for c in range(cols): board[r][c] = "O" if board[r][c] == "S" else "X"