LeetCode 130 Surrounded Regions - Implementation

DFS from border O's to mark safe. Flip remaining O's, restore safe ones.

function solve(board): if not board: return m, n = len(board), len(board[0])

def dfs(r, c):
    if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != 'O':
        return
    board[r][c] = 'S'
    dfs(r-1, c)
    dfs(r+1, c)
    dfs(r, c-1)
    dfs(r, c+1)

for i in range(m):
    dfs(i, 0)
    dfs(i, n-1)
for j in range(n):
    dfs(0, j)
    dfs(m-1, j)

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'

$O(m \cdot n)$ time.