Simple & Clear python BFS solution

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

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