BFS with deque, python 99ms


  • 0
    R
    from collections import deque
    class Solution(object):
        def solve(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            n = len(board)
            if n>0:
                m = len(board[0])
            else:
                m = 0
            markMatrix = [([0]) * m for i in range(n)]
            extend = deque()
            for i in xrange(n):
                if board[i][0] == 'O':
                    extend.append([i,0])
                    markMatrix[i][0] = 1
                if board[i][m - 1] == 'O':
                    extend.append([i,m - 1])
                    markMatrix[i][m - 1] = 1
            for i in xrange(m):
                if board[0][i] == 'O':
                    extend.append([0,i])
                    markMatrix[0][i] = 1
                if board[n-1][i] == 'O':
                    extend.append([n - 1, i])
                    markMatrix[n - 1][i] = 1
            while extend:
                item = extend.popleft()
                i = item[0]
                j = item[1]
                if i + 1 < n:
                    if markMatrix[i + 1][j] == 0 and board[i + 1][j] == 'O':
                        extend.append([i + 1, j])
                        markMatrix[i + 1][j] = 1
                if i - 1 >= 0:
                    if markMatrix[i - 1][j] == 0 and board[i - 1][j] == 'O':
                        extend.append([i - 1, j])
                        markMatrix[i - 1][j] = 1
                if j + 1 < m:
                    if markMatrix[i][j + 1] == 0 and board[i][j + 1] == 'O':
                        extend.append([i, j + 1])
                        markMatrix[i][j + 1]= 1
                if j - 1 >= 0:
                    if markMatrix[i][j - 1] == 0 and board[i][j - 1] == 'O':
                        extend.append([i, j - 1])
                        markMatrix[i][j - 1] = 1
            for i in xrange(n):
                for j in xrange(m):
                    if markMatrix[i][j] == 1:
                        board[i][j] = 'O'
                    else:
                        board[i][j] = 'X'
    

Log in to reply
 

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