200 ms python solution using BFS


  • 0
    Y
    from collections import deque
    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):
            if not board:
                return
            board[:]=[list(x) for x in board]
            def dfs(i,j):
                queue=deque([])
                board[i][j]='V'
                queue.append((i,j))
                
                while queue:
                    i,j=queue.popleft()
                    if i-1>=0 and board[i-1][j]=='O':
                        board[i-1][j]='V'
                        queue.append((i-1,j))
                    if i+1<len(board) and board[i+1][j]=='O':
                        board[i+1][j]='V'
                        queue.append((i+1,j))
                    if j-1>=0 and board[i][j-1]=='O':
                        board[i][j-1]='V'
                        queue.append((i,j-1))
                    if j+1<len(board[0]) and board[i][j+1]=='O':
                        board[i][j+1]='V'
                        queue.append((i,j+1))
            
            
            for i in [0,len(board)-1]:
                for j in range(len(board[0])):
                    if board[i][j]=='O':
                            dfs(i,j)
                
            for i in range(len(board)):
                for j in [0,len(board[0])-1]:
                    if board[i][j]=='O':
                            dfs(i,j)
                
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j]=='V':
                    board[i][j]='O'
                elif board[i][j]=='O':
                    board[i][j]='X'
            
        board[:]=[''.join(x) for x in board]

Log in to reply
 

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