python - surrounded regions


  • 0
    S
    class Solution(object):
        def solve(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            rows = len(board)
            if rows:
                cols = len(board[0])
            else:
                return
            queue = []
            
            # find un-enclosed O
            for r in xrange(rows):
                for c in xrange(cols):
                    if (r in [0, rows-1] or c in [0, cols-1]) and board[r][c] == "O":
                        queue.append((r,c))
                        
            # find the neighbors of un-enclosed O
            while queue:
                r,c = queue.pop()
                if -1 < r < rows and -1 < c < cols and board[r][c] == "O":
                    board[r][c] = "V"
                    queue.append((r-1,c))
                    queue.append((r+1,c))
                    queue.append((r,c-1))
                    queue.append((r,c+1))
            
            # flip
            for r in xrange(rows):
                for c in xrange(cols):
                    if board[r][c] == "V":
                        board[r][c] = "O"
                    elif board[r][c] == "O":
                        board[r][c] = "X"
    

Log in to reply
 

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