My passed python solution, 704ms.


  • 2
    L

    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'

  • 0
    K

    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?


  • 0
    L

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


  • 0

    From the comments:

    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).


Log in to reply
 

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