# BFS
def solve(self, board):
queue = collections.deque([])
for r in xrange(len(board)):
for c in xrange(len(board[0])):
if (r in [0, len(board)1] or c in [0, len(board[0])1]) and board[r][c] == "O":
queue.append((r, c))
while queue:
r, c = queue.popleft()
if 0<=r<len(board) and 0<=c<len(board[0]) and board[r][c] == "O":
board[r][c] = "D"
queue.append((r1, c)); queue.append((r+1, c))
queue.append((r, c1)); queue.append((r, c+1))
for r in xrange(len(board)):
for c in xrange(len(board[0])):
if board[r][c] == "O":
board[r][c] = "X"
elif board[r][c] == "D":
board[r][c] = "O"
Python short BFS solution.


You can always give a wellreadable version code! But why this method costs almost 200 ms, which is slower than other DFS version? I can't see why, can you give me a hint?
BTW, instead of use this condition "if 0<=r<len(board) and 0<=c<len(board[0])" after we push an element, I choose to use this condition before which can speed up like 20ms.