https://leetcode.com/problems/the-maze-ii/#/description
bfs solution with queue
class Solution(object):
def shortestDistance(self, maze, start, destination):
"""
:type maze: List[List[int]]
:type start: List[int]
:type destination: List[int]
:rtype: bool
"""
m = len(maze)
n = len(maze[0])
res = None
def go(start, direction):
# return the stop position and length
i, j = start
x, y = direction
l = 0
while 0 <= i + x < m and 0 <= j + y < n and maze[i + x][j + y] != 1:
i += x
j += y
l += 1
return l, (i, j)
# bfs (dijkstra: https://en.wikipedia.org/wiki/Dijkstra's_algorithm)
visited = {}
q = [(0, tuple(start))]
while q:
length, cur = q.pop(0)
if cur in visited and visited[cur] <= length:
continue # if cur is visited and with a shorter length, skip it.
# visited all its neighbors
for direction in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
l, np = go(cur, direction)
q.append((length + l, np)) # push it into queue
# mark it as visited
visited[cur] = length
if tuple(destination) not in visited:
return -1
else:
return visited[tuple(destination)]
bfs solution with heap(PQ)
class Solution(object):
def shortestDistance(self, maze, start, destination):
"""
:type maze: List[List[int]]
:type start: List[int]
:type destination: List[int]
:rtype: bool
"""
m=len(maze)
n=len(maze[0])
res=None
def go(start, direction):
# return the stop position and length
i, j = start
x, y= direction
l=0
while 0 <= i+x < m and 0 <= j+y < n and maze[i+x][j+y] != 1:
i += x
j += y
l +=1
return l, (i,j)
# bfs (dijkstra: https://en.wikipedia.org/wiki/Dijkstra's_algorithm)
visited={}
q=[]
heapq.heappush(q, (0, tuple(start)))
while q:
length, cur = heapq.heappop(q)
if cur in visited:
continue # if 'cur' is visited skip it.
# the length with 'cur' is the shotest path from start to 'cur'
if cur == tuple(destination):
return length
# visited all its neighbors
for direction in [(-1, 0), (1, 0), (0,-1), (0,1)]:
l, np = go(cur, direction)
heapq.heappush(q, (length+l, np)) # push it into queue
# mark it as visited, 'length' is the shortest path from start to 'cur'
visited[cur] = length
return -1
