Simple & Clear python BFS solution


  • 0
    J
    1.Using two queues to representes pacific and atlantic
    2. BFS each of the queue
    3. Return the overlap
    
    def pacificAtlantic(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[List[int]]
        """
        import collections
        if not matrix: return []
        width, height = len(matrix[0]),len(matrix)
        pacific = [[False for j in range(width)] for i in range(height)]
        atlantic = [[False for j in range(width)] for i in range(height)]
        frontier_1 = collections.deque()
        frontier_2 = collections.deque()
        #col
        for i in range(height):
            pacific[i][0] = True
            frontier_1.append((i,0))
            atlantic[i][width-1] = True
            frontier_2.append((i,width-1))
        #row
        for j in range(width):
            pacific[0][j] = True
            frontier_1.append((0,j))
            atlantic[height-1][j] = True
            frontier_2.append((height-1,j))
        
        self.bfs(matrix, width, height, frontier_1, pacific)
        #print "pacific", pacific
        self.bfs(matrix, width, height, frontier_2, atlantic)
        #print "atlantic", atlantic
        res = []
        for i in range(height):
            for j in range(width):
                if pacific[i][j] and atlantic[i][j]:
                    res.append([i,j])
        return res
    
    def bfs(self, matrix, width, height, frontier, visited):
        while frontier:
            #print frontier
            for _ in range(len(frontier)):
                u = frontier.popleft()
                x,y = u[0],u[1]
                #four dictection
                if x - 1 >= 0 and matrix[x][y] <= matrix[x-1][y] and not visited[x-1][y]:
                    visited[x-1][y] = True
                    frontier.append((x-1,y))
                if y + 1 < width and matrix[x][y] <= matrix[x][y+1] and not visited[x][y+1]:
                    visited[x][y+1] = True
                    frontier.append((x,y+1))
                if x + 1 < height and matrix[x][y] <= matrix[x+1][y] and not visited[x+1][y]:
                    visited[x+1][y] = True
                    frontier.append((x+1,y))
                if y - 1 >= 0 and matrix[x][y] <= matrix[x][y-1] and not visited[x][y-1]:
                    visited[x][y-1] = True
                    frontier.append((x,y-1))
        return

Log in to reply
 

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