Hard

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

LAB

Grid directions are 1=right, 2=left, 3=down, 4=up. Return the minimum changes needed for a path from top-left to bottom-right.

EXAMPLES

Example 1

FUNCTION SHAPE

grid: intMatrix→int

SOLUTION NOTE

I actually don't know why this is a hard problem. It is just a standard dijkstra / 0-1 bfs solution. There are 2 cases, we either modify this cell (cost 1) to some other direction, or we keep the current direction of the arrow. (cost 0) This indicates 0-1 BFS.

Reveal reference solution +

pythonREFERENCE

# Dijkstra's approach
def minCost(self, grid: List[List[int]]) -> int:
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    m,n = len(grid), len(grid[0])

    pq = [(0,0,0)] # (cost, i,j)

    def isInBounds(i,j):
        return 0<=i<m and 0<=j<n

    while pq:
        cost, i,j = heappop(pq)

        if grid[i][j] == -1: continue
        tmp = grid[i][j]
        grid[i][j] = -1

        if (i,j) == (m-1,n-1): return cost

        # 1/2. combine logic. follow/modify the arrow
        for x,y in dirs:
            i_,j_ = i+x,j+y
            if isInBounds(i_,j_): heappush(pq, (cost+int((x,y) != dirs[tmp-1]), i_, j_))

    return -1

# 0-1 BFS (more optimal)
def minCost(self, grid: List[List[int]]) -> int:
    dq = deque([(0,0,0)])
    while dq:
        cost, i,j = dq.popleft()
        if grid[i][j] == -1: continue
        if (i,j) == ((m:=len(grid))-1,(n:=len(grid[0]))-1): return cost
        for k,(x,y) in enumerate([(0,1),(0,-1),(1,0),(-1,0)]):
            if 0<=(i_:=i+x)<m and 0<=(j_:=j+y)<n:
                if k == grid[i][j]-1: # edge cost is 0, append left
                    dq.appendleft((cost, i_,j_))
                else: # edge cost is 1, append right
                    dq.append((cost+1, i_,j_))
        grid[i][j] = -1

TimeO(m*n)

SpaceO(m*n)

Open on LeetCode ↗