1091. Shortest Path in Binary Matrix | 1658

 1class Solution:
 2    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
 3        if grid[0][0] != 0:
 4            return -1
 5
 6        n = len(grid)
 7        graph = {}  # (1, x, y) means distance == 1 at row x, col y
 8
 9        def possiblePaths(coord):
10            x, y = coord
11            result = []
12            # right
13            if y + 1 < n and grid[x][y + 1] == 0:
14                result.append((1, x, y + 1))
15            # bottom-right
16            if x + 1 < n and y + 1 < n and grid[x + 1][y + 1] == 0:
17                result.append((1, x + 1, y + 1))
18            # bottom
19            if x + 1 < n and grid[x + 1][y] == 0:
20                result.append((1, x + 1, y))
21            # bottom-left
22            if x + 1 < n and y - 1 > -1 and grid[x + 1][y - 1] == 0:
23                result.append((1, x + 1, y - 1))
24            # left
25            if y - 1 > -1 and grid[x][y - 1] == 0:
26                result.append((1, x, y - 1))
27            # top-left
28            if x - 1 > -1 and y - 1 > -1 and grid[x - 1][y - 1] == 0:
29                result.append((1, x - 1, y - 1))
30            # top
31            if x - 1 > -1 and grid[x - 1][y] == 0:
32                result.append((1, x - 1, y))
33            # top-right
34            if x - 1 > -1 and y + 1 < n and grid[x - 1][y + 1] == 0:
35                result.append((1, x - 1, y + 1))
36
37            return result
38
39        for x in range(n):
40            for y in range(n):
41                if grid[x][y] == 0:
42                    graph[(x, y)] = possiblePaths((x, y))
43
44        dist = {coord: float("inf") for coord in graph.keys()}
45        dist[(0, 0)] = 1
46
47        # prev = {coord: None for coord in graph.keys()}
48
49        pq = [(1, (0, 0))]
50        heapq.heapify(pq)
51
52        visited = set()
53
54        while pq:
55            current_dist, current_node = heapq.heappop(pq)
56
57            if current_node in visited:
58                continue
59
60            visited.add(current_node)
61
62            if current_node == (n - 1, n - 1):
63                return current_dist
64
65            for weight, x, y in graph[current_node]:
66                neighbor = (x, y)
67                new_dist = current_dist + weight
68
69                if new_dist < dist[neighbor]:
70                    dist[neighbor] = new_dist
71                    # prev[neighbor] = current_node
72                    heapq.heappush(pq, (new_dist, neighbor))
73
74        return -1