Minimum Cost to Make at Least One Valid Path in a Grid

Problem Id: 1368 Difficulty: Hard Tag: Breadth-first Search


Intuition

We could use BFS to solve this problem. Each time, we choose a node with the lowest cost and search all its neighbours. So the cost of each node would always be the minimum cost to get to the node.

Solution


import heapq


class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        cost = [[float('inf')] * n for _ in range(m)]
        heap = [[0, m - 1, n - 1]]
        while heap:
            c, i, j = heapq.heappop(heap)
            if c < cost[i][j]:
                cost[i][j] = c
                if i - 1 >= 0:
                    tmp = c
                    if grid[i - 1][j] != 3:
                        tmp += 1
                    heapq.heappush(heap, [tmp, i - 1, j])
                if i + 1 < m:
                    tmp = c
                    if grid[i + 1][j] != 4:
                        tmp += 1
                    heapq.heappush(heap, [tmp, i + 1, j])
                if j - 1 >= 0:
                    tmp = c
                    if grid[i][j - 1] != 1:
                        tmp += 1
                    heapq.heappush(heap, [tmp, i, j - 1])
                if j + 1 < n:
                    tmp = c
                    if grid[i][j + 1] != 2:
                        tmp += 1
                    heapq.heappush(heap, [tmp, i, j + 1])
        return cost[0][0]