AC Python 140 ms solution, BFS starting from boundary 'O'


  • 4
    displacements = [[1, 0], [-1, 1], [-1, -1], [1, -1]]
    # (i,j) -> (i+1,j) -> (i,j+1) -> (i-1,j) -> (i,j-1)
    
    def bfs(self, board, i, j, m, n):
        # O: White, X:Black, G:Gray
        dq = collections.deque([[i, j]])
        board[i][j] = 'G'
        while dq:
            i, j = dq.popleft()
            for di, dj in Solution.displacements:
                i += di
                j += dj
                if 0 <= i < m and 0 <= j < n and board[i][j] == 'O':
                    dq.append([i, j])
                    board[i][j] = 'G'
    
    def solve(self, board):
        if len(board) < 3 or len(board[0]) < 3:
            return
        m, n = len(board), len(board[0])
        for i in xrange(m):
            for j in 0, n - 1:
                if board[i][j] == 'O':
                    self.bfs(board, i, j, m, n)
    
        for i in 0, m - 1:
            for j in xrange(1, n - 1):
                if board[i][j] == 'O':
                    self.bfs(board, i, j, m, n)
    
        for row in board:
            for j in xrange(n):
                if row[j] != 'X':
                    row[j] = 'X' if row[j] == 'O' else 'O'
    
    # 58 / 58 test cases passed.
    # Status: Accepted
    # Runtime: 140 ms
    # 94.63%
    

    The idea is to color all non surrounded region and then flip those uncolored ones. Any non surrounded region must connect to a 'O' at the boundary. Therefore we can perform BFS from boundary 'O's. This way we minimized our search task.


  • 0
    A

    Here I have a problem, why do you keep incrementing i and j in each direction?
    My understanding is that you should do something like

    for di, dj in Solution.displacements:
            tmpi = i + di
            tmpj = j + dj
    

    to avoid i, and j being in the wrong direction

    for di, dj in Solution.displacements:
            i += di
            j += dj
    

  • 0

    If i did wrong i won't get AC right?

    I know it is a bit of confusing here. Thanks for asking.

    I did use a trick, note that I didn't use directions which should be:

    directions = [[1, 0], [-1,0], [0,1],[0,-1]]
    

    Instead I used this

    displacements = [[1, 0], [-1, 1], [-1, -1], [1, -1]]
    

    see the difference?


  • 0
    A

    Got it, thanks.


Log in to reply
 

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