# BFS with heap, python

• We use a heap instead a queue to do the BFS.

In this way the first hit to the destination is guaranteed to be the shortest path.

``````class Solution(object):
def shortestDistance(self, maze, start, destination):
"""
:type maze: List[List[int]]
:type start: List[int]
:type destination: List[int]
:rtype: int
"""
if not maze or not maze[0]:
return -1

self.M,self.N=len(maze),len(maze[0])

self.Min=self.M*self.N+1

Visit=[[0 for _ in range(0,self.N)] for __ in range(0,self.M)]

import heapq
Heap=[]
heapq.heappush( Heap, (0,start[0],start[1]) )

while(Heap):
#print(Heap)
length,i,j=heapq.heappop(Heap)

if length>self.Min:
continue
if Visit[i][j]==1:
continue
if [i,j]==destination:
return length

Visit[i][j]=1

I=i
J=j
Path=0
while(I+1<self.M and maze[I+1][J]!=1):
I+=1
Path+=1

heapq.heappush( Heap,(length+Path,I,J) )

I=i
J=j
Path=0
while(I-1>=0 and maze[I-1][J]!=1):
I-=1
Path+=1
heapq.heappush( Heap,(length+Path,I,J) )

I=i
J=j
Path=0
while(J+1<self.N and maze[I][J+1]!=1):
J+=1
Path+=1
heapq.heappush(Heap, (length+Path,I,J) )

I=i
J=j
Path=0
while(J-1>=0 and maze[I][J-1]!=1):

J-=1
Path+=1

heapq.heappush( Heap,(length+Path,I,J) )

return -1

`````````

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