Shortest Path in Binary Matrix (Leetcode 1091)

Problem Link: https://leetcode.com/problems/shortest-path-in-binary-matrix/

from collections import defaultdict
import heapq
class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        
        # Dijkstra's Algorithm
        
        m=len(grid)
        n=len(grid[0])
        if(grid[0][0]==1 or grid[m-1][n-1]==1):
            return -1
        pq=[]
        heapq.heapify(pq)
        distance=[[float('inf') for i in range(n)] for j in range(m)]
        distance[0][0]=1
        # (i,j,dist)
        heapq.heappush(pq,(0,0,1))
        
        while(len(pq)>0):
            
            curri,currj,dist=heapq.heappop(pq)
            
            for x, y in ((curri-1,currj-1),(curri-1,currj),(curri-1,currj+1),(curri,currj-1),(curri,currj+1),(curri+1,currj-1),(curri+1,currj),(curri+1,currj+1)):
                if(x in range(0,m) and y in range(0,n) and grid[x][y]==0):
                    if(distance[curri][currj]+1<distance[x][y]):
                        distance[x][y]=distance[curri][currj]+1
                        heapq.heappush(pq,(x,y,distance[x][y]))
        
        if(distance[m-1][n-1]==float('inf')):
            return -1
        return distance[m-1][n-1]

Last updated