You are given an m x n board of "X" and "O". A region of "O" cells (connected up, down, left, right) is surrounded if none of its cells is on the border of the board. Capture every surrounded region by turning all its "O" cells into "X". Modify the board in place; the function returns nothing.
"O" on the bottom edge is on the border, so it stays.- 1 <= m, n <= 200
- board[i][j] is "X" or "O"
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Checking each region separately to see if it touches the border works but is fiddly. Flip the question: an "O" survives only if it is connected to an `"O"` on the border. So start from every border "O", flood its region and mark those cells with a temporary symbol like "#". After that, any "O" still on the board cannot reach the border, so it is surrounded and becomes "X". Finally turn the "#" cells back into "O".
Algorithm
- Push every
"O"on the four borders onto a stack and mark it"#". - Flood from them: any neighbour that is
"O"becomes"#"and is pushed. - Scan the whole board: change
"O"to"X"(captured) and"#"back to"O"(safe).
O(m * n)Space: O(m * n) for the stack in the worst case"O" can go 40000 calls deep and overflow the stack in Java or Python. An explicit stack or queue avoids that.class Solution: def solve(self, board: List[List[str]]) -> None: m, n = len(board), len(board[0]) stack = [] # Every border O is safe for r in range(m): for c in range(n): if (r in (0, m - 1) or c in (0, n - 1)) and board[r][c] == "O": board[r][c] = "#" stack.append((r, c)) # Everything connected to a safe cell is safe too while stack: r, c = stack.pop() for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == "O": board[nr][nc] = "#" stack.append((nr, nc)) # Capture the rest, restore the safe cells for r in range(m): for c in range(n): if board[r][c] == "O": board[r][c] = "X" elif board[r][c] == "#": board[r][c] = "O"