LeetCode 1368. 使网格图至少有一条有效路径的最小代价
目录
题目描述
题意分析
给定
m × n的网格，每个格子里画着一个箭头：1指右、2指左、3指下、4指上。从左上角(0,0)出发，站在某格时只能沿着这一格的箭头方向走到相邻格。允许花费 1 的代价把任意一格的箭头改成任意方向，同一格可以改但改了就固定。问让(0,0)能走到(m-1, n-1)的最小总代价。把「修改箭头」这件事重新表述一下，题目立刻清晰：站在
(x, y)想去某个相邻格，如果目标方向恰好是当前格的箭头方向，这一步免费；否则需要花 1 把箭头掰过去。也就是说每个格子仍然有四条出边，只是其中一条权为 0、另外三条权为 1。于是问题变成一张
m × n个点、每点四条出边、边权只有 0 和 1 的图上的单源最短路。「边权只有 0 和 1」是本题最强的信号，它比一般的正权图多出一层结构，可以让复杂度从 $O(mn \log(mn))$ 降到 $O(mn)$。要注意修改的是当前格的箭头而不是目标格的：代价取决于你从哪一格往哪个方向迈，与落点格子里画着什么无关。搞反这一点会让整套转移全错。
约束里
m, n最大 100，格子总数一万，箭头值保证在1..4之间。规模不大，但因为是困难题，考的是能否识别出 0-1 边权这个结构并给出线性解法。边界要留意四点：起点就是终点（
m = n = 1）时代价为 0；答案一定存在，因为任何格子花 1 就能掰向任意方向，最坏也能走通；可以往回走（四个方向都允许，不限于右和下）；同一格可能被多次经过，但改箭头的代价只在「从它迈出的那一步」计一次。
解法：0-1 BFS
核心思路
先把图建清楚：点是格子，边是「从
(x,y)迈到相邻格(nx,ny)」，权是grid[x][y]的箭头是否指向那个方向——指向则 0，否则 1。求的是从(0,0)到(m-1,n-1)的最短路。这个建模没有把同一格的修改费重复计算：边权非负，因此最优方案总能删去环，选成一条不重复经过格子的简单路径；简单路径只从每个格子离开一次，修改该格箭头恰好对应那条出边的 1 次费用。
最直接的做法是 Dijkstra，用优先队列按距离取最小，复杂度 $O(mn \log(mn))$。这完全能过，但没有利用边权的特殊性。
朴素 BFS 为什么不行？普通 BFS 的「首次访问即确定最短距离」依赖所有边权相同。这里有 0 权边，先进先出的队列可能让距离较大的节点先出队；若仍在首次入队时锁定节点，就会错过后续更短路径。
观察到边权只有 0 和 1：从距离为
d的状态松弛出去，新距离只可能是d或d + 1。因此用双端队列代替最小堆：0 权边的新状态插队首，1 权边的新状态插队尾。队首始终是当前最小距离，这就是 0-1 BFS，可视为 Dijkstra 的两桶特化。不变量是：双端队列中状态携带的距离单调不减，尚未处理的最小距离位于队首。 弹出
d后，0 权候选仍为d，放队首；1 权候选为d + 1，放队尾，所以顺序保持。由 Dijkstra 的贪心性质，某格第一次以未过期的最小距离出队时，该距离已经确定。
dist数组的定义是：dist[i][j]表示从起点到达格子(i,j)的当前已知最小代价，初值为无穷大，dist[0][0] = 0。松弛条件写成严格小于：只有d + cost < dist[nx][ny]时才更新并入队。这一条同时承担了「去重」和「防止无限循环」两个职责——因为四个方向包含往回走，格子之间会互相指向，没有这道闸门就会反复入队。队列状态保存
(x, y, d)。同一格可能在正式出队前被更短路径再次松弛，因此弹出时若d != dist[x][y]，它就是旧状态，直接跳过；这就是惰性删除。通过检查后的状态才扩展邻边，也可以在此时安全地提前返回终点距离。终点第一次以未过期状态出队时即可返回。终点一定可达，因为始终可以修改箭头沿一条相邻格路径走过去。
正确性说明：每条边的 0/1 权值与是否修改出发格箭头完全一致，所以路径权值就是修改次数。双端队列规则保证未过期的最小距离状态优先出队；严格松弛又允许后来发现的更短路径覆盖旧值。按 Dijkstra 的贪心结论，终点第一次以未过期状态出队时距离已最优，因此返回值就是最少修改次数。
解题步骤
- 把
dist初始化为m * n，并令dist[0][0] = 0。 最优路径可取简单路径，至多经过m * n - 1条边，因此这个值严格大于任何合法答案，又避免了最大整数参与加法的风险。- 定义方向数组，并让下标与箭头编号严格对应。 题目规定
1右、2左、3下、4上，所以dirs必须按{{0,1},{0,-1},{1,0},{-1,0}}的顺序排列，判断grid[x][y] == i + 1才成立。顺序写错会让「免费方向」张冠李戴，这是本题最隐蔽的错误。- 把状态
(0, 0, 0)放入双端队列，每次从队首弹出。 若状态携带的d不等于当前dist[x][y]，说明它已经过期，直接跳过；否则它就是当前最小距离。若此时到达终点，可以立即返回d。- 枚举四个方向，先做越界检查。 四个方向都要试，包括往左和往上。只走右和下是把这题当成了网格 DP，但箭头可能把你逼得必须绕行，限制方向会漏掉最优解。
- 代价判定写成
cost = (grid[x][y] == i + 1) ? 0 : 1。 用的是起点格的箭头，不是落点格的。判断依据是「从(x,y)迈向第i个方向要不要改箭头」。- 松弛条件用严格小于，满足才更新并入队。 相等时不入队，否则同一距离的节点会被反复推进队列导致死循环。这一条替代了传统 BFS 的
visited数组，功能更强：它允许一个格子在找到更优路径时被重新处理。cost == 0插队首，cost == 1插队尾。 这是保持距离顺序的关键；只有状态按这个规则入队，终点出队时才能立即确定最优值。- 终点的未过期状态出队时返回距离。 题目保证通过修改总能到达终点；循环后的返回值只是满足编译器的兜底。
以
grid = [[1,1,3],[3,2,2],[1,1,4]]走一遍（正确答案是 0）。箭头含义：第 0 行是右、右、下；第 1 行是下、左、左；第 2 行是右、右、上。初始
dist[0][0] = 0，队列为[(0,0,0)]。弹出
(0,0,0)，箭头是 1（右）。向右到(0,1)的边权为 0，状态(0,1,0)插队首；向下到(1,0)的边权为 1，状态(1,0,1)插队尾。队列从前到后的距离为 0、1。接着免费状态始终被放到队首，依次得到
(0,1) → (0,2) → (1,2) → (1,1) → (1,0) → (2,0) → (2,1) → (2,2)，所有状态距离都是 0。途中(1,1)、(1,0)曾先以距离 1 入队，后来又被免费路径更新为 0；旧的距离 1 状态出队时会被d != dist[x][y]跳过。终点状态
(2,2,0)从队首弹出时没有过期，立即返回 0。这条蛇形路径全程顺着箭头，验证了 0 权边必须优先处理。反例
grid = [[1,2],[4,3]]的答案是 1：先免费向右，再花 1 把右上角箭头改为向下。若把普通 BFS 的「首次入队即锁定」套到 0/1 权图上，较贵路径可能先占住节点，后续免费改进无法生效。
代码实现
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
class Solution {
public int minCost(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist) {
Arrays.fill(row, m * n);
}
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
Deque<int[]> dq = new ArrayDeque<>();
dist[0][0] = 0;
dq.offerFirst(new int[] {0, 0, 0});
while (!dq.isEmpty()) {
int[] cur = dq.pollFirst();
int x = cur[0];
int y = cur[1];
int d = cur[2];
if (d != dist[x][y]) {
continue;
}
if (x == m - 1 && y == n - 1) {
return d;
}
for (int direction = 0; direction < 4; direction++) {
int nx = x + dirs[direction][0];
int ny = y + dirs[direction][1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
continue;
}
int cost = grid[x][y] == direction + 1 ? 0 : 1;
int nextDist = d + cost;
if (nextDist >= dist[nx][ny]) {
continue;
}
dist[nx][ny] = nextDist;
int[] next = {nx, ny, nextDist};
if (cost == 0) {
dq.offerFirst(next);
} else {
dq.offerLast(next);
}
}
}
return -1;
}
}
import "container/list"
func minCost(grid [][]int) int {
m, n := len(grid), len(grid[0])
dist := make([][]int, m)
for i := range dist {
dist[i] = make([]int, n)
for j := range dist[i] {
dist[i][j] = m * n
}
}
dirs := [4][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
type state struct {
x, y, dist int
}
dq := list.New()
dist[0][0] = 0
dq.PushFront(state{0, 0, 0})
for dq.Len() > 0 {
cur := dq.Remove(dq.Front()).(state)
if cur.dist != dist[cur.x][cur.y] {
continue
}
if cur.x == m-1 && cur.y == n-1 {
return cur.dist
}
for direction, move := range dirs {
nx, ny := cur.x+move[0], cur.y+move[1]
if nx < 0 || nx >= m || ny < 0 || ny >= n {
continue
}
cost := 1
if grid[cur.x][cur.y] == direction+1 {
cost = 0
}
nextDist := cur.dist + cost
if nextDist >= dist[nx][ny] {
continue
}
dist[nx][ny] = nextDist
next := state{nx, ny, nextDist}
if cost == 0 {
dq.PushFront(next)
} else {
dq.PushBack(next)
}
}
}
return -1
}
复杂度分析
- 时间复杂度：$O(V + E) = O(mn)$。每个未过期状态只扩展一次，每次检查 4 条出边；每次成功松弛至多产生一个队列状态，数量为 $O(E)$。相比堆优化 Dijkstra 的 $O(E \log V)$，双端队列省去了对数因子。
- 空间复杂度：$O(V + E) = O(mn)$，包括距离数组与双端队列中的状态；网格图有 $V = mn$ 个点、$E < 4mn$ 条边。
关键点总结
- 把「修改代价」翻译成「边权」是解题的第一步：一旦意识到「顺着箭头走权 0、其余三个方向权 1」，题目就从一道构造题变成了标准最短路。凡是「花代价改变规则以达成目标」的题，都可以试着把代价搬到边上。
- 边权只有 0 和 1 时用双端队列代替堆：0 权边入队首、1 权边入队尾，出队顺序仍按距离单调不减，复杂度从 $O(E \log V)$ 降到 $O(V + E)$。这是 Dijkstra 的一个重要特化，值得单独记住。
- 松弛条件是严格变小：0/1 权图中，同一格可能先得到较大距离、随后被 0 权路径改进；首次入队就永久标记会漏解。
- 状态携带入队时距离，弹出时检查是否过期：若
state.dist != dist[x][y]就跳过。这样无需在双端队列中查找旧项，也不会用旧距离重复扩展。- 方向数组的顺序必须与题目编号对齐：
dirs[i]与箭头值i+1的对应关系是本题唯一的「题目特定」细节，写代码前先把1=右 2=左 3=下 4=上抄在旁边比事后调试快得多。- 面试视角：先完成图建模，再说明 Dijkstra 可行；随后利用边权仅为 0/1，将 0 权候选放队首、1 权候选放队尾，使队首始终保持最小距离。能把这个不变量和严格松弛条件讲清楚，比只背模板更重要。
易错点总结
- 错误写法：把 0 权边也插到队尾，再按普通 BFS 首次访问就锁定 → 在
grid = [[1,1,3],[3,2,2],[1,1,4]]中，某些格子先以代价 1 入队，后续代价 0 的改进被拒绝，最终返回 1 而不是 0。- 错误写法：把 0 权和 1 权的插入位置写反 → 较大距离反而被优先处理，破坏「队首距离最小」的不变量，终点首次出队时不再能保证最优。
- 错误写法：用
visited数组代替松弛条件，访问过就不再处理 → 用例grid = [[1,1,3],[3,2,2],[1,1,4]]中(1,1)先以代价 1 被访问并标记，之后从(1,2)过来的免费路径无法再更新它，最终答案返回 1 而正确答案是 0。- 错误写法：代价判断用落点格的箭头
grid[nx][ny] == i + 1→ 用例grid = [[1,1,1],[2,2,2],[1,1,1]]中转移代价全部算反，答案与正确值完全不符。- 错误写法：方向数组写成
{{1,0},{-1,0},{0,1},{0,-1}}（下上右左） → 与题目1=右 2=左 3=下 4=上的编号错位，用例grid = [[1,1,3],[3,2,2],[1,1,4]]中本该免费的向右移动被算成代价 1，返回 2 而正确答案是 0。- 错误写法：只枚举右和下两个方向 → 用例
grid = [[1,1,3],[3,2,2],[1,1,4]]的最优路径需要在第 1 行从右往左走，限制方向后走不出这条路，返回大于 0 的值。- 错误写法：松弛条件写成
d + cost <= dist[nx][ny]→ 相等时也入队，两个互相可达且距离相同的格子会无限互相推入队列，程序死循环。- 低效写法：状态携带距离，却不做过期检查 → 较大距离的旧状态仍会枚举四条出边；严格松弛通常能守住正确性，但会产生不必要的扩展，且不能安全地在终点首次弹出时直接返回。
- 错误写法：
dist初始化为 0 而不是无穷大 → 任意用例下所有松弛条件d + cost < 0恒不成立，队列弹空后直接返回dist[m-1][n-1] = 0，对本例侥幸正确，但对答案非 0 的用例（如grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]，答案 3）会返回 0。- 错误写法：越界判断只写
nx < m && ny < n漏掉负数下限 → 用例中从(0,0)向左或向上扩展会访问grid[-1][0]，数组越界异常。- 遗漏建模依据：担心一条路径重复经过同一格后修改费用无法按边累计 → 边权非负，最优路线总能删去环变成简单路径；每个格子至多离开一次，因此每条 1 权边与一次改箭头一一对应。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 743. 网络延迟时间 | 中等 | 一般正权图的 Dijkstra 模板，边权任意所以必须用优先队列 |
| 787. K 站中转内最便宜的航班 | 中等 | 多出「中转次数」这一维约束，需要 Bellman-Ford 按轮松弛而非 Dijkstra |
| 1631. 最小体力消耗路径 | 中等 | 路径代价是边权最大值而非求和，Dijkstra 的松弛式要改成取 max |
| 778. 水位上升的泳池中游泳 | 困难 | 同为「最小化路径最大值」，也可用二分答案配合连通性判定 |
| 1293. 网格中的最短路径 | 困难 | 状态要加上「剩余可消除障碍数」，边权全为 1 所以用普通 BFS 即可 |
| 1129. 颜色交替的最短路径 | 中等 | 状态附带「上一条边的颜色」，同样是把约束塞进状态维度的思路 |
| 505. 迷宫 II | 中等 | 球会一直滚到撞墙，一次转移跨越多格，边权是滚动距离，需要 Dijkstra |
| 499. 迷宫 III | 困难 | 在最短距离基础上还要求路径字典序最小，比较键变成二元组 |
| 1091. 二进制矩阵中的最短路径 | 中等 | 八方向且边权全为 1，是可以用朴素 BFS 的对照组 |
| 64. 最小路径和 | 中等 | 只能右和下所以无环，可以直接 DP；本题因为允许四向移动才必须上最短路 |
| 174. 地下城游戏 | 困难 | 同为网格最优化，但状态要逆向定义成「所需初始值」，正向 DP 会失效 |
| 994. 腐烂的橘子 | 中等 | 多源 BFS 且边权全为 1，起点是所有腐烂格，适合对比单源与多源的初始化差异 |
| 815. 公交路线 | 困难 | 把路线而非站点当作节点建图，考察建模视角的转换 |
| 1345. 跳跃游戏 IV | 困难 | 隐式图上的等权最短路，重点是按值建索引并及时清空避免边数爆炸 |