Problem statement

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

Solution 1

We can look at this problem as graph problem, where weight of arrow is 0 and all other 3 directions are 1. Then we can use Dijkstra algorithm.

Complexity

Time complexity is O(mn*log(mn)) and space complexity is O(mn).

Code

class Solution:
    def minCost(self, grid):
        m, n = len(grid), len(grid[0])
        neibs = [(1, 1, 0), (2, -1, 0), (3, 0, 1), (4, 0, -1)]
        dist = [[float('inf')] * n for _ in range(m)]
        dist[0][0] = 0
        heap = [(0, 0, 0)]
        
        while heap:
            steps, x, y = heappop(heap)
            if (x, y) == (n - 1, m - 1): return steps
            
            for dr, dx, dy in neibs:
                if 0 <= x + dx < n and 0 <= y + dy < m:
                    cand = dist[y][x] + (dr != grid[y][x])
                    if cand < dist[y + dy][x + dx]:
                        dist[y + dy][x + dx] = cand
                        heappush(heap, (w + steps, x + dx, y + dy))

Solution 2

There is better algorithm. The idea is so-called 0-1 graph bfs, where when we meet the zero edge, we put to the left of deque and if we have one, we put the the end. Also we need to use not visited set, but dists like in Dijkstra, because we can return to some nodes, but only if distance is reduced. See also 1263 problem where I used similar idea.

Complexity

Time and space is O(mn).

Code

class Solution:
    def minCost(self, grid):
        m, n = len(grid), len(grid[0])
        neibs = [(1, 1, 0), (2, -1, 0), (3, 0, 1), (4, 0, -1)]
        Q = deque([(0, 0, 0)])
        dist = [[float('inf')] * n for _ in range(m)]
        dist[0][0] = 0
        
        while Q:
            steps, x, y = Q.popleft()
            if (x, y) == (n - 1, m - 1): return steps
            
            for dr, dx, dy in neibs:
                if 0 <= x + dx < n and 0 <= y + dy < m:
                    w = (dr != grid[y][x])
                    cand = dist[y][x] + w
                    if cand < dist[y + dy][x + dx]:
                        dist[y + dy][x + dx] = cand
                    
                        if w == 0:
                            Q.appendleft((steps, x + dx, y + dy))
                        else:
                            Q.append((steps + 1, x + dx, y + dy))