Leetcode 1485 Solution

This article provides solution to leetcode question 1485 (minimum-cost-to-make-at-least-one-valid-path-in-a-grid)
Categories:
Tags:
Access this page by simply typing in "lcs 1485" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid

Solution

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = []
        heapq.heappush(q, (0, 0, 0))
        visited = set((0, 0))
        while q:
            cost, cx, cy = heapq.heappop(q)



            if (cx, cy) in visited:
                continue



            visited.add((cx, cy))



            if cx == m - 1 and cy == n - 1:
                return cost
            for dx, dy in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                nx, ny = cx + dx, cy + dy
                if nx < 0 or nx >= m or ny < 0 or ny >= n or (nx, ny) in visited:
                    continue
                if (dy == 1 and grid[cx][cy] == 1) or (dy == -1 and grid[cx][cy] == 2) or (dx == 1 and grid[cx][cy] == 3 or dx == -1 and grid[cx][cy] == 4):
                    heapq.heappush(q, (cost, nx, ny))
                else:
                    heapq.heappush(q, (cost + 1, nx, ny))