# Python PriorityQueue Solution

• ``````from Queue import PriorityQueue
class Solution(object):
def shortestDistance(self, maze, start, destination):
"""
:type maze: List[List[int]]
:type start: List[int]
:type destination: List[int]
:rtype: int
"""
visited = set()
m, n = len(maze), len(maze[0])
queue = PriorityQueue()
queue.put((0, tuple(start)))
dis = [None]
while not queue.empty():
next_tgt = queue.get()
pos, curr_dis = next_tgt[1], next_tgt[0]
if pos in visited: continue
if pos == tuple(destination):
dis[0] = curr_dis
break
visited.add(pos)
i, j = pos
right_j = left_j = j
up_i = down_i = i
while right_j < n and maze[i][right_j] == 0: right_j += 1
while left_j >= 0 and maze[i][left_j] == 0: left_j -= 1
while down_i < m and maze[down_i][j] == 0: down_i += 1
while up_i >= 0 and maze[up_i][j] == 0: up_i -= 1
queue.put((curr_dis + right_j - 1 - j, (i, right_j-1)))
queue.put((curr_dis + j - 1 - left_j, (i, left_j+1)))
queue.put((curr_dis+ i - 1 - up_i, (up_i+1, j)))
queue.put((curr_dis + down_i - 1 - i, (down_i-1, j)))

return dis[0] if dis[0] else -1

``````

• Hi, I am trying to re-implement it using deque in python. The code is like

``````class Solution(object):
def shortestDistance(self, maze, start, destination):
"""
:type maze: List[List[int]]
:type start: List[int]
:type destination: List[int]
:rtype: int
"""
# BFS
visited = set()
m, n = len(maze), len(maze[0])
q = collections.deque([(0, tuple(start))])
dis = None
while q:
curr_dis, pos = q.popleft()
if pos in visited: continue
if pos == tuple(destination):
dis = curr_dis
break
visited.add(pos)
i, j = pos
right_j = left_j = j
up_i = down_i = i
while right_j < n and maze[i][right_j] == 0: right_j += 1
while left_j >= 0 and maze[i][left_j] == 0: left_j -= 1
while down_i < m and maze[down_i][j] == 0: down_i += 1
while up_i >= 0 and maze[up_i][j] == 0: up_i -= 1
q.append((curr_dis + right_j - 1 - j, (i, right_j-1)))
q.append((curr_dis + j - 1 - left_j, (i, left_j+1)))
q.append((curr_dis+ i - 1 - up_i, (up_i+1, j)))
q.append((curr_dis + down_i - 1 - i, (down_i-1, j)))

return dis if dis else -1
``````

but it does not pass all the tests( failed at test 68). Can anyone lend me a hand? thanks!

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