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