# 200 ms python solution using BFS

• ``````from collections import deque
class Solution:
# @param board, a 2D array
# Capture all regions by modifying the input board in-place.
# Do not return any value.
def solve(self, board):
if not board:
return
board[:]=[list(x) for x in board]
def dfs(i,j):
queue=deque([])
board[i][j]='V'
queue.append((i,j))

while queue:
i,j=queue.popleft()
if i-1>=0 and board[i-1][j]=='O':
board[i-1][j]='V'
queue.append((i-1,j))
if i+1<len(board) and board[i+1][j]=='O':
board[i+1][j]='V'
queue.append((i+1,j))
if j-1>=0 and board[i][j-1]=='O':
board[i][j-1]='V'
queue.append((i,j-1))
if j+1<len(board[0]) and board[i][j+1]=='O':
board[i][j+1]='V'
queue.append((i,j+1))

for i in [0,len(board)-1]:
for j in range(len(board[0])):
if board[i][j]=='O':
dfs(i,j)

for i in range(len(board)):
for j in [0,len(board[0])-1]:
if board[i][j]=='O':
dfs(i,j)

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

board[:]=[''.join(x) for x in board]``````

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