Python BFS solution


  • 0
    P
    import Queue
    
    class Solution(object):
        def pacificAtlantic(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[List[int]]
            """
            self.m = len(matrix)
            if self.m == 0:
                return []
            self.n = len(matrix[0])
            q = Queue.PriorityQueue()
            visited = [[0 for i in range(0, self.n)] for j in range(0, self.m)]
            toPacific = set()
            for i in self.initStates(0, matrix):
                q.put(i)
            while q.empty() != True:
                cell = q.get()
                if visited[cell[1]][cell[2]] == 1:
                    continue
                else:
                    visited[cell[1]][cell[2]] = 1
                    toPacific.add((cell[1], cell[2]))
                for next in self.nextStates(matrix, cell[1], cell[2]):
                    if matrix[next[0]][next[1]] >= cell[0]:
                        q.put((matrix[next[0]][next[1]], next[0], next[1]))
            
            q = Queue.PriorityQueue()
            visited = [[0 for i in range(0, self.n)] for j in range(0, self.m)]
            toAtlantic = set()
            for i in self.initStates(1, matrix):
                q.put(i)
            while q.empty() != True:
                cell = q.get()
                if visited[cell[1]][cell[2]] == 1:
                    continue
                else:
                    visited[cell[1]][cell[2]] = 1
                    toAtlantic.add((cell[1], cell[2]))
                for next in self.nextStates(matrix, cell[1], cell[2]):
                    if matrix[next[0]][next[1]] >= cell[0]:
                        q.put((matrix[next[0]][next[1]], next[0], next[1]))
            
            ansSet = toPacific & toAtlantic
            ans = []
            for i in ansSet:
                ans.append([i[0], i[1]])
            return ans
        
        def nextStates(self, matrix, x, y):
            dirX = [1, 0, -1, 0]
            dirY = [0, 1, 0, -1]
            l = []
            for i in range(0, 4):
                newX = x + dirX[i]
                newY = y + dirY[i]
                if newX >= 0 and newX < self.m and newY >= 0 and newY < self.n:
                    l.append((newX, newY))
            return l
        
        def initStates(self, no, matrix):
            l = []
            if no == 0:
                for i in range(0, self.n):
                    l.append((matrix[0][i], 0, i))
                for i in range(1, self.m):
                    l.append((matrix[i][0], i, 0))
            else:
                for i in range(0, self.n):
                    l.append((matrix[self.m - 1][i], self.m - 1, i))
                for i in range(0, self.m - 1):
                    l.append((matrix[i][self.n - 1], i, self.n - 1))
            return l
    

Log in to reply
 

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