# Python BFS solution

• ``````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
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
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
``````

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