My passed python solution, 704ms.

• It's Easy to understand, just scan from all direction, if has change, then rescan the matrix.

``````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):
width = len(board)
if(width <= 0):return
height = len(board[0])

scan = 1
while(scan == 1):
scan=0

#from top->bottom scan.
for i in range(width):
for j in range(height):
if(board[i][j] == 'O' and (i == 0 or board[i - 1][j] == 'k')):
board[i][j] = 'k'
scan=1;

#from left->right scan.
for i in range(height):
for j in range(width):
if(board[j][i] == 'O' and (i == 0 or board[j][i-1] == 'k')):
board[j][i] = 'k'
scan=1;
#from bottom->top scan.
for i in range(width - 1,-1,-1):
for j in range(height - 1,-1,-1):
if(board[i][j] == 'O' and (i == width - 1 or board[i + 1][j] == 'k')):
board[i][j] = 'k'
scan=1;
#from right->left scan.
for i in range(height-1,-1,-1):
for j in range(width-1,-1,-1):
if(board[j][i] == 'O' and (i == height - 1 or board[j][i+1] == 'k')):
board[j][i] = 'k'
scan=1;

for i in range(height- 1,-1,-1):
for j in range(width - 1,-1,-1):
if(board[j][i] == 'k'):
board[j][i] = 'O'
else:
board[j][i] = 'X'``````

• It works, though it seems that the complexity is similar to bfs.

for a 2D array of mn, your algorithm complexity is about 5(mn), right?

• Yes, I think it's O(mn).

I think it's O(mn).

With m and n being height and width, it's O((mn)^2). Consider this board (space instead of 'O' for easy viewing):

``````# #############################################
# #   #   #   #   #   #   #   #   #   #   #   #
#   #   #   #   #   #   #   #   #   #   #   # #
############################################# #
#   #   #   #   #   #   #   #   #   #   #   # #
# #   #   #   #   #   #   #   #   #   #   #   #
# #############################################
# #   #   #   #   #   #   #   #   #   #   #   #
#   #   #   #   #   #   #   #   #   #   #   # #
############################################# #
#   #   #   #   #   #   #   #   #   #   #   # #
# #   #   #   #   #   #   #   #   #   #   #   #
# #############################################
# #   #   #   #   #   #   #   #   #   #   #   #
#   #   #   #   #   #   #   #   #   #   #   # #
############################################# #
#   #   #   #   #   #   #   #   #   #   #   # #
# #   #   #   #   #   #   #   #   #   #   #   #
###############################################
``````

In each while-loop iteration, you only progress a handful of cells. So you need O(mn) while-loop iterations, and each of them takes O(mn).

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