Description
Modify an X/O board by changing every O-region that cannot reach a board edge into X. Connections are horizontal or vertical. Examples show the resulting board.
Solution
def solve(board):
rows, cols = len(board), len(board[0])
stack = []
def mark(r, c):
if board[r][c] == "O":
board[r][c] = "#"
stack.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 stack:
r, c = stack.pop()
for x, y in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= x < rows and 0 <= y < cols:
mark(x, y)
for r in range(rows):
for c in range(cols):
board[r][c] = "O" if board[r][c] == "#" else "X"Examples
Example 1
- Input
[[["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"]]
Only the bottom border O is safe.
Example 2
- Input
[[["O"]]]- Output
[["O"]]
A one-cell region touches the edge.
Example 3
- Input
[[["O","O"],["O","O"]]]- Output
[["O","O"],["O","O"]]
Every cell is connected to a border.
Approach
Flood-fill O-cells reachable from any border and temporarily mark them safe. A final pass captures remaining O-cells and restores the safe markers to O.
Time & space
O(rc) time and O(rc) auxiliary space, where r and c are board dimensions; the board is changed in place.