Medium Border DFS Graphs
In plain English: Flip all O regions to X, except those connected to the border of the board.
Reverse thinking: instead of finding surrounded regions, find unsurrounded ones. DFS/BFS from all border 'O's, marking them safe. Then flip all remaining 'O' to 'X' and restore safe cells.
Prompt
Given an m x n board of 'X' and 'O', capture all regions of 'O' that are completely surrounded by 'X' (flip them to 'X'). Border-connected 'O's should not be captured.
Try to write it from scratch before scrolling down.
Solution
def solve(board):
if not board:
return
m, n = len(board), len(board[0])
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
return
board[i][j] = 'S' # mark as safe
dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
# Mark border-connected O's as safe
for i in range(m):
dfs(i, 0); dfs(i, n - 1)
for j in range(n):
dfs(0, j); dfs(m - 1, j)
# Flip: O -> X (captured), S -> O (safe)
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'S':
board[i][j] = 'O'
return board
# Test: solve([["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"]]