Python BFS


  • 0
    N

    I was trying to use DFS to solve this problem during Contest, and got TLE. After reading https://discuss.leetcode.com/topic/83453/java-solution-bfs, I found how idiotic I am, why didn't I ever think about BFS?

    Here is the solution using the same trick as https://discuss.leetcode.com/topic/29054/easiest-java-solution-with-explanation.

    class Solution(object):
        def helper(self, matrix, height, width, x, y):
            dirs = ((0,1), (0,-1), (1,0), (-1,0))
            queue = collections.deque([(x, y)])
            step = 0
            while queue:
                for _ in xrange(len(queue)):
                    x, y = queue.popleft()
                    if x < 0 or x >= height or y < 0 or y >= width:
                        continue
                    if matrix[x][y] & 1 == 0:
                        return step
                    for d_x, d_y in dirs:
                        queue.append((x+d_x, y+d_y))
                step += 1
            
            
        def updateMatrix(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[List[int]]
            """
            height = len(matrix)
            width = len(matrix[0])
            for i in xrange(height):
                for j in xrange(width):
                    if matrix[i][j] != 0:
                        matrix[i][j] |= (self.helper(matrix, height, width, i, j) << 1)
            
            for i in xrange(height):
                for j in xrange(width):
                    if matrix[i][j] != 0:
                        matrix[i][j] >>= 1
            return matrix
    

Log in to reply
 

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