# Python readable solution, DFS + Stack

• Since direct DFS would cause maximum depth error, I optimized the answer with stack.

``````class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
for i in range(len(board)):
if board[i][0] == "O":
self.dfs(board, [(i,0)])
if board[i][-1] == "O":
self.dfs(board, [(i, len(board[0])-1)])
for j in range(len(board[0])):
if board[0][j] == "O":
self.dfs(board, [(0, j)])
if board[-1][j] == "O":
self.dfs(board, [(len(board) - 1, j)])

for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'I':
board[i][j] = 'O'

def dfs(self, board, stack):
round = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while stack:
i,j = stack.pop()
board[i][j] = 'I'
for (x, y) in round:
nI, nJ = i + x, j + y
if 0 <= nI < len(board) and 0 <= nJ < len(board[0]) and board[nI][nJ] == 'O':
stack += [(nI, nJ)]

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.