Today’s problem

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

Intuition

Consider a question:

Here, there is a graph, each edge has a value 1 or 0, and you should travel from point 0 to point N, what is the shortest path?

In this case, you would quickly think of graph algorithms such as Dijkstra, SPFA, or even BFS.

But what if I tell you that the question above is the exact same question as what we are solving this quesion? Can you quickly think of the transition between the setting in the question and the setting in this more simple version?

Now, some of you may think that this problem may be DP question: we have a grid, we may be able to write a DP formular…

But wait, the most important prerequisite of DP is aftereffect. To run a DP, you must make sure that there is not aftereffect. In our situation, because we may need to go from right to left, from down to top, so aftereffect exists. Therefore, we cannot use DP in this question.

Approach

Now, to transfer our question to the question above, we only need to iterate through the graph and create an edge between a point to its neighbor, if this is the neighbor it is pointing at, then the value of the edge will be 0, otherwise it would be 1.

Some of you may consern the correctness of this solution, as there is also a limitation that “You can modify the sign on a cell one time only”.

However, the situation is, this graph has not negative edges, which means that your result will always increase if you go through more points. Therefore, you will not even vist the same point more than 1 time, so it is impossible for the solution you get to change the sign of a cell more than 1 time.

Now, run your Dijkstra (or other shortest path algorithms), and you are all set!

Complexity

• Time complexity: $O(N\times M\times log(N\times M))$

• Space complexity: $O(N\times M)$

Code

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]
        n,m = len(grid), len(grid[0])
        edges = [[] for i in range(n * m)]
        def cordinate2d21d(x,y):
            return x * m + y
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                pos = cordinate2d21d(i, j)
                for idx in range(4):
                    nx = i + dx[idx]
                    ny = j + dy[idx]
                    if nx < 0 or ny < 0 or nx >= n or ny >= m:
                        continue
                    npos = cordinate2d21d(nx, ny)
                    if idx + 1 == grid[i][j]:
                        edges[pos].append([npos, 0])
                    else:
                        edges[pos].append([npos, 1])

        dis = [inf] * (n * m)
        dis[0] = 0
        q = [(0,0)]

        while q:
            d, x = heappop(q)
            for to, v in edges[x]:
                if d + v < dis[to]:
                    dis[to] = d + v
                    heappush(q, (dis[to], to))

        return dis[cordinate2d21d(n-1, m-1)]