Python short BFS solution.


  • 15
    C
    # BFS
    def solve(self, board):
        queue = collections.deque([])
        for r in xrange(len(board)):
            for c in xrange(len(board[0])):
                if (r in [0, len(board)-1] or c in [0, len(board[0])-1]) and board[r][c] == "O":
                    queue.append((r, c))
        while queue:
            r, c = queue.popleft()
            if 0<=r<len(board) and 0<=c<len(board[0]) and board[r][c] == "O":
                board[r][c] = "D"
                queue.append((r-1, c)); queue.append((r+1, c))
                queue.append((r, c-1)); queue.append((r, c+1))
            
        for r in xrange(len(board)):
            for c in xrange(len(board[0])):
                if board[r][c] == "O":
                    board[r][c] = "X"
                elif board[r][c] == "D":
                    board[r][c] = "O"

  • 0
    H

    You can always give a well-readable version code! But why this method costs almost 200 ms, which is slower than other DFS version? I can't see why, can you give me a hint?

    BTW, instead of use this condition "if 0<=r<len(board) and 0<=c<len(board[0])" after we push an element, I choose to use this condition before which can speed up like 20ms.


  • 2
    C

    he did not have to append all things to deque, could check boarder first, and save time.


  • 0
    H

    I think that your solution deserve more up votes!


Log in to reply
 

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