Do a DFS from the nodes on the edges to solve this problem.
from collections import deque
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board:
return
m = len(board)
n = len(board[0])
queue = deque([])
for i in range(m):
if board[i][0] == 'O':
queue.append([i, 0])
board[i][0] = 'o'
if board[i][n - 1] == 'O':
queue.append([i, n - 1])
board[i][n - 1] = 'o'
for j in range(n):
if board[0][j] == 'O':
queue.append([0, j])
board[0][j] = 'o'
if board[m - 1][j] == 'O':
queue.append([m - 1, j])
board[m - 1][j] = 'o'
while queue:
i, j = queue.popleft()
for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
if not (0 <= x < m and 0 <= y < n):
continue
if board[x][y] == 'O':
board[x][y] = 'o'
queue.append([x, y])
for i in range(m):
for j in range(n):
board[i][j] = 'O' if board[i][j] == 'o' else 'X'