LeetCode 1368. 使网格图至少有一条有效路径的最小代价 题目描述 给你一个 m x n 的网格图 grid。网格图的每个格子 (i, j) 中都有一个数字，数字的范围是 1 到 4，分别表示从该格子出发的箭头的方向： 1 表示向右（即指向格子 (i, j + 1)） 2 表示向左（即指向格子 (i, j - 1)） 3 表示向下（即指向格子 (i + 1, j)） 4 表示向上（即指向格子 (i - 1, j)） 你可以“修改”任意一个格子的数字，每次修改的“代价”为 1。修改后，这个格子的箭头方向可以变成 1 到 4 中的任意一个。 你需要从网格图的左上角格子 (0, 0) 出发，沿着箭头指示的方向移动，目标是最终能够到达右下角的格子 (m-1, n-1)。如果从 (0, 0) 开始，按照箭头走，无法走到 (m-1, n-1)，你就需要修改一些箭头的方向，使得至少存在一条从 (0, 0) 到 (m-1, n-1) 的有效路径。 请你计算并返回所需的最“小”修改代价。 示例： 输入：grid = [ [ 1,1,1,1],[ 2,2,2,2],[ 1,1,1,1],[ 2,2,2,2] ] 输出：3 解释：最少需要修改 3 个格子的箭头方向才能从 (0,0) 走到 (3,3)。 解题过程循序渐进讲解 第一步：问题理解与转化 核心问题是：从起点 (0,0) 到终点 (m-1, n-1)，每个格子有一个初始的、指向四个方向之一的箭头。我们可以“免费”沿着箭头走到下一个格子。如果我们想改变行走方向（即不按照当前格子的箭头走），就需要付出 1 点代价（相当于修改了当前格子的箭头，使其指向我们想去的方向）。 目标：找到一条从起点到终点的路径，使得需要“改变方向”的次数（即修改格子的次数）最少。 我们可以把这个问题转化成一个“图论”中的“最短路径”问题： 每个格子是一个“节点”。 从一个节点到另一个节点的“边”带有“权值”（即代价）： 如果从节点 A 到节点 B 的方向，恰好等于节点 A 中箭头标注的方向，那么走这条边的代价是 0（免费）。 否则，从节点 A 到节点 B 需要修改 A 的箭头，代价是 1。 这样，问题就变成了：在一个有向图上（每个节点有 4 条出边，分别指向上下左右四个邻接格子，但每条边的权重不同），求从起点到终点的“最短路径”（即路径上所有边的权重之和最小）。 第二步：图模型与算法选择 每个节点 (i, j) 最多有 4 条出边，指向其上下左右的邻居（如果邻居在网格内）。每条出边的权重为： 如果出边的方向等于 grid[ i][ j ] 的值（1右，2左，3下，4上），则权重为 0。 否则，权重为 1。 现在，我们需要在一个 边权只有 0 和 1 的有向图上，求单源最短路径（从起点到所有点的最短距离，我们最终关心到终点的距离）。 这是一个典型的“0-1 BFS”（也称为“双端队列 BFS”）适用场景。因为如果边权只有 0 和 1，我们可以用比 Dijkstra 算法更高效的方法来求最短路： 使用一个 双端队列 deque。 当从当前节点 u 扩展到一个新节点 v 时： 如果边 (u, v) 的权重是 0，则将节点 v 加入到 deque 的 前端 （类似 BFS 的同层扩展）。 如果边 (u, v) 的权重是 1，则将节点 v 加入到 deque 的 后端 （类似 BFS 的下一层扩展）。 这样，deque 始终保持“距离起点更近的节点在前端”，可以保证第一次弹出某个节点时，得到的就是从起点到该节点的最短距离。 第三步：算法步骤详解 初始化： 网格大小 m = len(grid)， n = len(grid[ 0 ])。 距离数组 dist，大小 m x n，初始化为无穷大（表示未知距离）。dist[ 0][ 0 ] = 0。 双端队列 deque，初始将起点 (0, 0) 加入队列前端。 方向数组 dirs，用于方便地根据方向编号得到行偏移和列偏移。例如： dirs[ 1 ] = (0, 1) // 1: 右 dirs[ 2 ] = (0, -1) // 2: 左 dirs[ 3 ] = (1, 0) // 3: 下 dirs[ 4 ] = (-1, 0) // 4: 上 注意：这里我们让索引 1 到 4 对应题目中的箭头值，所以 dirs 数组大小为 5，索引 0 不用。 当 deque 不为空时循环： a. 从 deque 前端弹出一个节点 (i, j)。 b. 如果弹出的节点正好是终点 (m-1, n-1)，由于 0-1 BFS 的特性，此时 dist[ i][ j ] 已经是最小代价，可以直接返回（因为 BFS 按距离从小到大弹出，终点第一次弹出时距离最小）。 c. 遍历当前节点 (i, j) 的四个可能方向（对应四个邻居）： - 方向编号 k 从 1 到 4。 - 计算邻居坐标 (ni, nj) = (i + dirs[ k][ 0], j + dirs[ k][ 1 ])。 - 确保 (ni, nj) 在网格范围内。 d. 计算从当前节点 (i, j) 走到邻居 (ni, nj) 的“代价”： - 如果当前格子的箭头 grid[ i][ j ] 等于方向 k，则代价 cost = 0。 - 否则，cost = 1。 e. 如果通过当前节点 (i, j) 走到邻居 (ni, nj) 的“新距离” = dist[ i][ j] + cost 小于 邻居当前的 dist[ ni][ nj ]： - 更新 dist[ ni][ nj ] = 新距离。 - 根据 cost 的值决定插入 deque 的位置： - 如果 cost == 0，将邻居 (ni, nj) 插入到 deque 的前端。 - 如果 cost == 1，将邻居 (ni, nj) 插入到 deque 的后端。 循环结束，返回 dist[ m-1][ n-1 ]（最终一定会被更新，因为最坏情况下我们可以修改所有格子，代价有限）。 第四步：举例说明（以题目示例为例） grid = [ [ 1,1,1,1 ], [ 2,2,2,2 ], [ 1,1,1,1 ], [ 2,2,2,2] ] 起点 (0,0)，箭头是1（向右）。dist[ 0][ 0 ] = 0。 从 (0,0) 出发： 向右到 (0,1)：箭头一致，cost=0。dist[ 0][ 1 ] = 0，插入队列前端。 其他方向（左、下、上）都会出界或 cost=1，暂时不看。 弹出 (0,1)，箭头是1（右）。到 (0,2) cost=0，更新 dist[ 0][ 2 ]=0，前端插入。同理，从 (0,1) 可以到 (0,0) 但距离不会更优。 继续，会一直免费向右走到 (0,3)。dist[ 0][ 3 ]=0。 从 (0,3) 出发： 向右出界。 向下到 (1,3)：箭头是2（左），与方向“下”(3)不同，cost=1。新距离=0+1=1。更新 dist[ 1][ 3 ]=1，后端插入。 其他方向略。 之后，队列会先处理所有距离为0的节点（第一行），然后处理距离为1的节点... 关键点：从 (1,3)（距离1）可以向左到 (1,2)，箭头一致（2是左），cost=0，所以 dist[ 1][ 2 ] 可以更新为 1+0=1，前端插入。这样，第二行的点可以通过若干次免费左移到达。 最终，我们需要走到 (3,3)。路径可能类似：(0,0)右->(0,3) 代价0，然后必须向下（改方向）代价1到(1,3)，再向左到(1,2)代价0，再向下（改方向）代价1到(2,2)，再向右到(2,3)代价0，再向下（改方向）代价1到(3,3)。总代价=3。 算法会探索所有可能，并记录到每个点的最小代价，最终计算出最小总代价为3。 第五步：复杂度与总结 时间复杂度：O(m * n)。每个节点最多被插入和弹出 deque 常数次（每个节点可能因不同距离被更新多次，但 0-1 BFS 中，每个节点最多被更新一次，因为边权非负，且每次更新距离减小，最多更新常数次（不同距离））。实际上，每个节点通常只被处理一次。 空间复杂度：O(m * n)，用于 dist 数组和 deque。 核心思想 ：将原问题转化为在特殊权值（0或1）有向图中的单源最短路径问题，并利用 0-1 BFS 高效求解，避免了 Dijkstra 算法的 log 因子。