今日题目

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

解题思路

先思考这样一个问题：

有一张图，每条边的权值为 1 或 0，需要从节点 0 走到节点 N，求最短路径。

面对这道题，你应该很快就会想到 Dijkstra、SPFA 或 BFS 等图算法。

但如果我告诉你，上面这道题和我们要解决的题目本质上完全相同呢？你能迅速找到题目原始设定和这个简化版本之间的转换关系吗？

也许有些人会想到用动态规划来解：这是一个网格问题，似乎可以写出一个 DP 转移方程……

但是，DP 最重要的前提是无后效性。而在本题中，由于我们可能需要从右往左、从下往上移动，后效性是存在的。因此，本题不能使用 DP。

解题方法

将原题转化为上述简化版本的方法很直接：遍历整张图，在每个节点与其相邻节点之间建边——若该邻居恰好是当前节点箭头所指的方向，则边权为 0，否则边权为 1。

有些人可能会担心这个方案的正确性，因为题目还有一个限制：“每个格子的符号最多只能修改一次”。

然而，由于图中不存在负权边，意味着经过的节点越多，代价只会增加不会减少。因此在最优路径中，同一个节点不会被访问超过一次，也就不可能对同一个格子的符号修改超过一次，这个限制自然得到满足。

现在，直接跑 Dijkstra（或其他最短路算法）即可！

复杂度

  • 时间复杂度：$O(N\times M\times log(N\times M))$

  • 空间复杂度：$O(N\times M)$

代码

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)]