使网格图至少有一条有效路径的最小代价

难度: Hard

给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：

1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]

注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域。

一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径 不需要是最短路径 。

你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次 。

请你返回让网格图至少有一条有效路径的最小代价。

示例 1：

输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
输出：3
解释：你将从点 (0, 0) 出发。
到达 (3, 3) 的路径为： (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) 花费代价 cost = 1 使方向向下 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) 花费代价 cost = 1 使方向向下 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) 花费代价 cost = 1 使方向向下 --> (3, 3)
总花费为 cost = 3.

示例 2：

输入：grid = [[1,1,3],[3,2,2],[1,1,4]]
输出：0
解释：不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。

示例 3：

输入：grid = [[1,2],[4,3]]
输出：1

示例 4：

输入：grid = [[2,2,2],[2,2,2]]
输出：3

示例 5：

输入：grid = [[4]]
输出：0

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100

Submission

运行时间: 103 ms

内存: 17.1 MB

#这道题和上道题目是有区别的，上一道题目的节点只与自身节点有关，而在这道题目中，我所走的节点是与上一个节点有关系的
# 所以我可能直接就向下走了，代价加1，但这很有可能并不是最优的，我并不能直接去根据我是否最先到达最终节点来判断
# 因为我有可能我的最优解是在它的左边这个节点然后一路畅通的，这也就是本做法的问题所在，所以我们创建一个数组来记录新的值

# class Solution:
#     def minCost(self, grid: List[List[int]]) -> int:
#         #1 右 2左 3下 4上
#         visited=[[False]*len(grid[0]) for _ in range(len(grid))]
#         visited[0][0]=True
#         de=deque([[0,0]])
#         values=[[float('inf')]*len(grid[0]) for _ in range(len(grid))]
#         values[0][0]=0
#         dis=[[0,1],[0,-1],[1,0],[-1,0]]
#         while de:
#             x,y=de.popleft()
#             for i in range(4):
#                 nx,ny=x+dis[i][0],y+dis[i][1]
#                 if 0<=nx<len(grid) and 0<=ny<len(grid[0]):                
#                     if visited[nx][ny]==False or values[nx][ny]>values[x][y]+(1 if grid[x][y]!=i+1 else 0) :
#                         visited[nx][ny]=True
#                         if grid[x][y]==i+1:
#                             de.appendleft([nx,ny])
#                         else:
#                             de.append([nx,ny])
#                     values[nx][ny]=min(values[nx][ny],values[x][y]+(1 if grid[x][y]!=i+1 else 0))
#         return values[-1][-1]

class Solution:
    def minCost(self, A: List[List[int]]) -> int:
        n, m = len(A), len(A[0])
        dist = [[inf] * m for _ in range(n)]
        dist[0][0] = 0
        dq = deque([(0, 0)])
        while dq:
            x, y = dq.popleft()
            for nx, ny, op in (x, y + 1, 1), (x, y - 1, 2),(x + 1, y, 3), (x - 1, y, 4):
                if not(0 <= nx < n and 0 <= ny < m):
                    continue
                g = A[x][y]
                d=dist[x][y] + (1 if g != op else 0)
                if  dist[nx][ny] > d:
                    dist[nx][ny] = d
                    if g == op:#出现0代价的路线，优先加入队列头
                        dq.appendleft((nx, ny))
                    else:
                        dq.append((nx, ny))
        return dist[-1][-1]

Explain

题解采用了一种基于0-1广度优先搜索（BFS）的方法，结合了Dijkstra算法的特点。每个格子可以看作一个节点，格子中的数字决定了从该节点出发可以直接到达的邻接节点的方向。如果当前方向与格子内指定的方向一致，则移动代价为0；如果不一致，则需要修改方向，代价为1。算法从(0, 0)开始，使用双端队列存储待处理的节点，对于代价为0的移动优先处理（添加到队列前端），代价为1的移动则添加到队列末端。利用一个二维数组记录到每个节点的最小代价，不断更新这个数组直到找到到达(m-1, n-1)的最小代价。

时间复杂度: O(mn)

空间复杂度: O(mn)

# 定义Solution类

class Solution:
    def minCost(self, A: List[List[int]]) -> int:
        n, m = len(A), len(A[0])  # 获取网格的行数和列数
        dist = [[float('inf')] * m for _ in range(n)]  # 初始化距离数组，初始距离为无穷大
        dist[0][0] = 0  # 起点的代价为0
        dq = deque([(0, 0)])  # 使用双端队列，初始化包含起点
        while dq:  # 当队列不为空
            x, y = dq.popleft()  # 弹出队列首部元素
            for nx, ny, op in (x, y + 1, 1), (x, y - 1, 2),(x + 1, y, 3), (x - 1, y, 4):  # 检查四个可能的移动方向
                if not(0 <= nx < n and 0 <= ny < m):  # 判断新坐标是否越界
                    continue
                g = A[x][y]  # 当前格子指定的方向
                d = dist[x][y] + (1 if g != op else 0)  # 计算到达新坐标的代价
                if dist[nx][ny] > d:  # 如果找到了更小的代价
                    dist[nx][ny] = d  # 更新代价
                    if g == op:  # 如果移动方向与当前格子指定的方向一致，优先处理
                        dq.appendleft((nx, ny))
                    else:  # 否则，添加到队列末尾
                        dq.append((nx, ny))
        return dist[-1][-1]  # 返回到达终点的最小代价

Explore

在题解中，0-1 BFS 结合了 Dijkstra 算法的特点，具体优化来自于处理代价为0和代价为1的不同优先级。在传统的 BFS 中，所有的边都具有相同的权重，而在 Dijkstra 算法中，边的权重可以不同，且算法会选择累计代价最小的路径。在这个题解中，如果移动方向与当前格子指定的方向相同，代价为0，不相同则为1。通过在双端队列中使用不同的插入策略（代价为0的移动优先处理，插入到队列前端；代价为1的移动插入到队列末端），算法能够更快地找到代价最小的路径。这种处理方式实质上是在保证 BFS 的宽度遍历特性的同时，引入了优先考虑低代价移动的策略，从而达到了类似 Dijkstra 的效果。

在题解的代码实现中，将满足`g == op`条件的坐标对`(nx, ny)`添加到双端队列的前端，是因为这种移动的代价为0，代表可以'免费'移动到该节点。将这种移动放在队列前端可以确保这些节点能够被更快地处理，从而迅速扩展出代价最低的路径。相反，不满足条件的移动代价为1，这意味着其路径代价较高，因此被放在队列的末端，等待前面的低代价节点先被处理。这种处理显著优化了算法性能，因为它减少了在高代价路径上的不必要探索，让算法更倾向于沿着最小代价路径前进，从而在实际运行中能更快地找到最优解。

题解中提到的每个节点最多被访问和更新4次的结论基于每个节点最多有4个可能的移动方向（上、下、左、右）。在算法执行过程中，每个节点可能从任意一个相邻的节点接收到新的代价更新，因此在最坏的情况下，每个节点可能分别从四个方向被更新。但是，实际上每次更新都是基于找到更小的代价，一旦某方向的最小代价被发现并更新，该方向就不会再产生更高的代价更新。因此，虽然理论上一个节点在极端情况下可能被多次访问，实际上的访问次数通常受到有效路径和代价更新逻辑的限制。