1368. Minimum Cost to Make at Least One Valid Path in a Grid | 2069

 1class Solution:
 2    def minCost(self, grid: List[List[int]]) -> int:
 3        # adj
 4        # dist
 5        # pq
 6        # visited
 7        # dijkstra-able
 8        m, n = len(grid), len(grid[0])
 9
10        adj = defaultdict(list)  # (0, (1, 2))  cost, adj_cell
11        dist = {}
12
13        for i in range(m):
14            for j in range(n):
15                # write adj
16                # right
17                if j + 1 < n:
18                    if grid[i][j] == 1:
19                        adj[(i, j)].append((0, (i, j + 1)))
20                    else:
21                        adj[(i, j)].append((1, (i, j + 1)))
22                # down
23                if i + 1 < m:
24                    if grid[i][j] == 3:
25                        adj[(i, j)].append((0, (i + 1, j)))
26                    else:
27                        adj[(i, j)].append((1, (i + 1, j)))
28                # left
29                if j - 1 > -1:
30                    if grid[i][j] == 2:
31                        adj[(i, j)].append((0, (i, j - 1)))
32                    else:
33                        adj[(i, j)].append((1, (i, j - 1)))
34                # up
35                if i - 1 > -1:
36                    if grid[i][j] == 4:
37                        adj[(i, j)].append((0, (i - 1, j)))
38                    else:
39                        adj[(i, j)].append((1, (i - 1, j)))
40
41                # write dist
42                dist[(i, j)] = float("inf")
43
44        dist[(0, 0)] = 0
45
46        pq = [(0, (0, 0))]
47
48        while pq:
49            cost, pos = heapq.heappop(pq)
50
51            if cost > dist[pos]:
52                continue
53
54            if pos == (m - 1, n - 1):
55                return cost
56
57            for adj_cost, adj_pos in adj[pos]:
58                new_cost = cost + adj_cost
59                if new_cost < dist[adj_pos]:
60                    dist[adj_pos] = new_cost
61                    heapq.heappush(pq, (new_cost, adj_pos))
62
63        return -1  # impossible to reach