LeetCode 1368. 使网格图至少有一条有效路径的最小代价
题目描述
题意分析
网格每格有一个箭头，编号一、二、三、四分别指向右、左、下、上。希望从左上角沿箭头走到右下角，每修改一个格子的箭头花费一，求最少修改次数。
只需存在一条有效路径，不要求它的移动步数最少，也不要求修改后所有格子都能到终点。原箭头可能指向网格外，路径不能越界；到达终点后无需再离开，所以终点自己的箭头不会产生额外费用。
解法：0-1 BFS
核心思路
[!blue]
把每个格子看作图节点，与上下左右的合法邻居连有向边。从当前格沿原箭头方向走，费用为零；选择其他方向就要修改当前格箭头，费用为一。边权由出发格决定，不由落点决定。
这样一条简单路径的边权和就等于需要修改的格子数。图的边权非负，任何带环路线都能去掉重复的一段而不增加费用，所以总存在最优简单路径，每个格子最多离开一次。沿它设置箭头不会要求同一个格子反复改方向，符合每格只能修改一次的条件。
边权只有零和一，可以用双端队列实现最短路。
dist[x][y]表示目前找到的最低修改代价。从距离d的状态扩展，零费用邻居仍是d，放到队首尽快处理；一费用邻居是d + 1，放到队尾，排在当前更低代价的状态之后。这相当于按相邻距离层处理，不需要堆排序。不能在首次入队时就固定答案，因为之后可能找到更低费用的路线。只有
nextDist < dist[nx][ny]时才更新并入队，状态同时保存入队时的距离；出队后若该距离已不是当前dist，说明它已被更优状态替代，直接跳过。有效状态按最低代价优先扩展，非负边不能让后处理状态再改进已经确定的较小距离，因此终点有效状态出队时即可返回。严格改善才入队也避免零费用环反复推入同价状态；单格网格在起点出队时就返回零。
初始距离取
m * n足以大于最优值：一条不重复格子的路径最多有m * n - 1条边，每条代价至多一。搜索中只修改距离表，不需要实际改写原箭头。
解题步骤
- 将距离表初始化为
m * n，起点设为零并放入双端队列。- 弹出队首状态，若携带距离与当前距离表不符则跳过；若是终点则返回。
- 按右、左、下、上的编号顺序枚举四个合法邻居，根据出发格箭头计算零或一费用。
- 只有得到严格更小距离时才更新：零费用状态放队首，一费用状态放队尾。
- 持续处理直到终点的有效状态出队。
代码实现
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(mn)$，网格每格最多四条合法出边，0-1 BFS 为 $O(V+E)$。
- 空间复杂度：$O(mn)$，用于距离表和队列状态。
关键点总结
[!green]
- 一费用边对应修改出发格，最优简单路径让每格至多修改一次，完成题目与最短路的对应。
- 零费用放队首、一费用放队尾，维持低代价优先的处理顺序。
- 首次发现不代表最终最短，需要允许严格改善并跳过过期队列项。
- 方向编号必须与题面一致，左右上下四个方向都要考虑。
易错点总结
[!yellow]
- 按落点箭头判断费用，会把应由出发格决定的修改算错。
- 首次入队就永久锁定节点，可能拒绝后续零费用路线的改进。
- 两种费用都按普通 FIFO 并首次确定距离，无法保证最小代价先到。
- 相等距离也再次入队，会让零费用环重复制造无意义状态。
- 非起点距离初始化为零，所有非负候选都无法严格改善，搜索不能展开。
- 只尝试向右和向下会漏掉需要绕行的低费用路径。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1263. 推箱子 | 困难 | 两题都可转为0/1边权，本题沿箭头走免费、改方向付1，推箱题走路免费、推箱付1。 |
| 743. 网络延迟时间 | 中等 | 非负边权都可Dijkstra，但本题只有0和1两种权值，双端队列可进一步简化。 |