# My python solution

• Here is my python solution. ~ 500 ms. Not as fast as others' Java or C++ code. Not sure if it is because my implementation or the python interpreter.

``````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):

N = len(board)
if N <= 2: return

M = len(board[0])
if M <= 2: return

def dfs(i, j):
S = [(i, j)]    # dfs stack
while S:
p, q = S.pop()
board[p][q] = 'B'

# up, down, left, right
if p > 0 and board[p - 1][q] == 'O':        S.append((p - 1, q))
if p < N - 1 and board[p + 1][q] == 'O':    S.append((p + 1, q))
if q > 0 and board[p][q - 1] == 'O':        S.append((p, q - 1))
if q < M - 1 and board[p][q + 1] == 'O':    S.append((p, q + 1))

# top and bottom
for j in xrange(M):
if board[0][j] == 'O':      dfs(0, j)
if board[N - 1][j] == 'O':  dfs(N - 1, j)

# left and right
for i in xrange(1, N - 1):
if board[i][0] == 'O':      dfs(i, 0)
if board[i][M - 1] == 'O':  dfs(i, M - 1)

# final mark
for i in xrange(N):
for j in xrange(M):
if board[i][j] == 'O':      board[i][j] = 'X'
elif board[i][j] == 'B':    board[i][j] = 'O'``````

• like this solution!

• Here is mine:

``````def solve(self, board):
if not board:
return
not_captured = set()
m, n = len(board), len(board[0])
walls = list(itertools.product((0, m - 1), range(n))) + list(itertools.product(range(1, m - 1), (0, n - 1)))

# dfs from the edge
for i, j in walls:
if board[i][j] == 'O' and (i, j) not in not_captured:
self.dfs(i, j, not_captured, board)

# mark the captured
for i in range(1, m - 1):
for j in range(1, n - 1):
if board[i][j] == 'O' and (i, j) not in not_captured:
board[i][j] = 'X'

def dfs(self, i, j, table, board):
m, n = len(board), len(board[0])
is_valid = lambda x, y: -1 < x < m and -1 < y < n
stack = [(i, j)]
while stack:
i, j = stack.pop()
for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if is_valid(x, y) and board[x][y] == 'O' and (x, y) not in table:
stack.append((x, y))``````

• it is a typical BFS...

• My recursive DFS solution is as follows though Run Time Error in this oj test:

``````class Solution:
# @param {character[][]} board
# @return {void} Do not return anything, modify board in-place instead.
def solve(self, board):
if not board:
return
rows = len(board)
cols = len(board[0])
# merge Os on left&right border
for i in xrange(rows):
if board[i][0] == 'O':
self.merge(board, i, 0)
if board[i][cols-1] == 'O':
self.merge(board, i, cols-1)
# merge Os on top&bottom border
for j in xrange(cols):
if board[0][j] == 'O':
self.merge(board, 0, j)
if board[rows-1][j] == 'O':
self.merge(board, rows-1, j)
# process the board
for i in xrange(rows):
for j in xrange(cols):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '+':
board[i][j] = 'O'

def merge(self, board, i, j):
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != 'O':
return
board[i][j] = '+'

self.merge(board, i-1, j)
self.merge(board, i+1, j)
self.merge(board, i, j-1)
self.merge(board, i, j+1)
``````

My BFS solution passed the oj test with 192ms:

``````class Solution:
def __init__(self):
self.queue = []
# @param {character[][]} board
# @return {void} Do not return anything, modify board in-place instead.
def solve(self, board):
if not board:
return
rows = len(board)
cols = len(board[0])

for i in xrange(rows):
if board[i][0] == 'O':
self.bfs(board, i, 0)
if board[i][cols-1] == 'O':
self.bfs(board, i, cols-1)

for j in xrange(cols):
if board[0][j] == 'O':
self.bfs(board, 0, j)
if board[rows-1][j] == 'O':
self.bfs(board, rows-1, j)

for i in xrange(rows):
for j in xrange(cols):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '+':
board[i][j] = 'O'

def bfs(self, board, i, j):
n = len(board[0])
# fill current cell and then neighbors
self.fillCell(board, i, j)
while self.queue:
cur = self.queue[0]
self.queue = self.queue[1:]
x, y = cur / n, cur % n

self.fillCell(board, x-1, y)
self.fillCell(board, x+1, y)
self.fillCell(board, x, y-1)
self.fillCell(board, x, y+1)

def fillCell(self, board, i, j):
m, n = len(board), len(board[0])
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
return
# add current cell to queue and process neighbors in bfs
self.queue.append(i*n+j)
board[i][j] = '+'``````

• The post was indeed a BFS instead of DFS

No, it's obviously DFS, not BFS.

• @ManuelP Alright, my bad. I was a little bit confused when I glanced that all adjacent Os were found at one time. As BFS would process all those neighbors in the next round, the original post just processed one at a time, which should be DFS. Thanks for the correction:P

• I'm not quite sure what you mean with "process" and "the next round", but I'd say the main point is that it uses a stack rather than a queue. At least that's what I'm always looking for first.

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