# BFS with deque, python 99ms

• ``````from collections import deque
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
n = len(board)
if n>0:
m = len(board[0])
else:
m = 0
markMatrix = [([0]) * m for i in range(n)]
extend = deque()
for i in xrange(n):
if board[i][0] == 'O':
extend.append([i,0])
markMatrix[i][0] = 1
if board[i][m - 1] == 'O':
extend.append([i,m - 1])
markMatrix[i][m - 1] = 1
for i in xrange(m):
if board[0][i] == 'O':
extend.append([0,i])
markMatrix[0][i] = 1
if board[n-1][i] == 'O':
extend.append([n - 1, i])
markMatrix[n - 1][i] = 1
while extend:
item = extend.popleft()
i = item[0]
j = item[1]
if i + 1 < n:
if markMatrix[i + 1][j] == 0 and board[i + 1][j] == 'O':
extend.append([i + 1, j])
markMatrix[i + 1][j] = 1
if i - 1 >= 0:
if markMatrix[i - 1][j] == 0 and board[i - 1][j] == 'O':
extend.append([i - 1, j])
markMatrix[i - 1][j] = 1
if j + 1 < m:
if markMatrix[i][j + 1] == 0 and board[i][j + 1] == 'O':
extend.append([i, j + 1])
markMatrix[i][j + 1]= 1
if j - 1 >= 0:
if markMatrix[i][j - 1] == 0 and board[i][j - 1] == 'O':
extend.append([i, j - 1])
markMatrix[i][j - 1] = 1
for i in xrange(n):
for j in xrange(m):
if markMatrix[i][j] == 1:
board[i][j] = 'O'
else:
board[i][j] = 'X'
``````

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