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_j1)))
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_i1, j)))
return dis[0] if dis[0] else 1
Python PriorityQueue Solution


Hi, I am trying to reimplement 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_j1))) 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_i1, 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!