BFS with heap, python


  • 0
    B

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

Log in to reply
 

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