It's like a story


  • 0

    Those area connecting to the borders should not be modified. To do this:

    1. protect the border connecting area (BFS starting from the four border lines)
    2. kill those unprotected 'O's
    3. bring back the protected area
    class Solution(object):
        def solve(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            if not board:
                return 
            
            dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
            def mark(i, j, chr):
                queue = [(i, j)]
                while queue:
                    top = queue.pop()
                    i, j = top[0], top[1]
                    if not ( 0 <= i < len(board) and 0 <= j < len(board[0]) ) or board[i][j] != 'O':
                        continue
                    board[i][j] = chr
                    for l in xrange(len(dir)):
                        queue.append( (i + dir[l][0], j + dir[l][1]) )
            
            #protect left, right vertical borders
            for i in xrange(len(board)):
                if board[i][0] == 'O':
                    mark(i, 0, '1')
                if board[i][len(board[0]) - 1] == 'O':
                    mark(i, len(board[0]) - 1, '1')
            
            #protect top, bottom horizontal borders
            for i in xrange(len(board[0])):
                if board[0][i] == 'O':
                    mark(0, i, '1')
                if board[len(board) - 1][i] == 'O':
                    mark(len(board) - 1, i, '1')
                    
            #kill un-protected nodes
            for i in xrange(len(board)):
                for j in xrange(len(board[0])):
                    if board[i][j] == 'O':
                        board[i][j] = 'X'
            #bring back the protected nodes
            for i in xrange(len(board)):
                for j in xrange(len(board[0])):
                    if board[i][j] == '1':
                        board[i][j] = 'O'
    

Log in to reply
 

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