LeetCode 补充题 131. 四方向网格最短路径的构造
题目描述
[!green]
牛客原题： ✅ 补充题 131. 四方向网格最短路径的构造
给你一个矩形网格
grid，其中0表示可通行位置，1表示障碍，以及起点start和终点end的坐标。每步只能向上、下、左、右移动一格。请返回任意一条最短路径的坐标序列，包含起点和终点。坐标使用从
0开始的[行, 列]表示。如果终点不可达，或起点、终点位于障碍上，返回空列表。
示例 1：
输入：
grid = [[0,1,0],[0,0,0]], start = [0,0], end = [0,2]
输出：[[0,0],[1,0],[1,1],[1,2],[0,2]]
解释： 坐标按[行,列]表示且从0开始。该路径包含5个坐标，共移动4步，绕过障碍(0,1)。
提示：
-
牛客原题的起终点固定为左上角和右下角，并保证路径存在且唯一；本文将两端抽为参数，也支持一般的最短路径查询。
- 输入为矩形
01网格，坐标为从0开始的[行,列]。 - 只能上下左右移动。
- 结果包含起终点。
- 不可达或端点不可走时返回空列表。
题意分析
每次合法移动的代价都是 1，因此 BFS 首次发现一个格子时就得到了最少步数。本题还要返回具体路径，不能只统计距离，需要记下每个格子第一次从哪里到达。
解法：BFS 记录前驱并恢复路径
核心思路
[!blue]
将坐标
(r,c)编码为r * cols + c，用prev同时保存访问标记和前驱。未访问为 -1，起点的前驱设为自己，既标记已访问，也作为路径回溯的终点。按队列顺序扩展四个邻居，第一次发现可通行格子时立即登记前驱并入队。BFS 的距离逐层递增，此时记录的前驱来自上一层，所以沿这条链一定能恢复一条最短路；后续访问不覆盖它。
如果终点仍未访问，返回空结果。否则从终点沿前驱走到起点，逐个保存坐标后整体反转。起终点相同且可走时无需搜索，路径只包含该坐标；坐标个数始终比移动步数多 1。
解题步骤
- 检查网格及起终点是否可走，将起点入队并登记其前驱为自己。
- 弹出位置并检查四个邻居，第一次发现时记录前驱并入队。
- 终点不可达则返回空列表，否则沿前驱回到起点，再反转坐标序列。
代码实现
class Solution {
public List<int[]> shortestPath(int[][] grid, int[] start, int[] end) {
List<int[]> out = new ArrayList<>();
int rows = grid.length;
if (rows == 0 || grid[0].length == 0) {
return out;
}
int cols = grid[0].length;
if (start[0] < 0
|| start[0] >= rows
|| start[1] < 0
|| start[1] >= cols
|| end[0] < 0
|| end[0] >= rows
|| end[1] < 0
|| end[1] >= cols) {
return out;
}
if (grid[start[0]][start[1]] != 0 || grid[end[0]][end[1]] != 0) {
return out;
}
int source = start[0] * cols + start[1];
int target = end[0] * cols + end[1];
int[] prev = new int[rows * cols];
Arrays.fill(prev, -1);
prev[source] = source;
ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.add(source);
int[] dr = {
-1,
1,
0,
0
};
int[] dc = {
0,
0,
-1,
1
};
while (!queue.isEmpty() && prev[target] == -1) {
int u = queue.remove();
for (int d = 0; d < 4; d++) {
int r = u / cols + dr[d];
int c = u % cols + dc[d];
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != 0) {
continue;
}
int v = r * cols + c;
if (prev[v] != -1) {
continue;
}
prev[v] = u;
queue.add(v);
}
}
if (prev[target] == -1) {
return out;
}
for (int u = target; ; u = prev[u]) {
out.add(new int[] {
u / cols,
u % cols
});
if (u == source) {
break;
}
}
Collections.reverse(out);
return out;
}
}
func shortestPath(grid [][]int, start, end []int) [][]int {
out := [][]int{}
rows := len(grid)
if rows == 0 || len(grid[0]) == 0 {
return out
}
cols := len(grid[0])
if start[0] < 0 || start[0] >= rows || start[1] < 0 || start[1] >= cols || end[0] < 0 || end[0] >= rows || end[1] < 0 || end[1] >= cols {
return out
}
if grid[start[0]][start[1]] != 0 || grid[end[0]][end[1]] != 0 {
return out
}
source, target := start[0]*cols+start[1], end[0]*cols+end[1]
prev := make([]int, rows*cols)
for i := range prev {
prev[i] = -1
}
prev[source] = source
queue := []int{
source,
}
dr, dc := []int{
-1,
1,
0,
0,
}, []int{
0,
0,
-1,
1,
}
for head := 0; head < len(queue) && prev[target] == -1; head++ {
u := queue[head]
for d := 0; d < 4; d++ {
r, c := u/cols+dr[d], u%cols+dc[d]
if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != 0 {
continue
}
v := r*cols + c
if prev[v] != -1 {
continue
}
prev[v] = u
queue = append(queue, v)
}
}
if prev[target] == -1 {
return out
}
for u := target; ; u = prev[u] {
out = append(out, []int{
u / cols,
u % cols,
})
if u == source {
break
}
}
for l, r := 0, len(out)-1; l < r; l, r = l+1, r-1 {
out[l], out[r] = out[r], out[l]
}
return out
}
复杂度分析
- 时间复杂度：$O(rows\cdot cols)$。
- 空间复杂度：额外空间 $O(rows\cdot cols)$。
关键点总结
[!green]
前驱既是访问标记，也是恢复最短路的证据；路径坐标数等于移动步数加一。
易错点总结
[!yellow]
- 必须在入队时标记，避免同一位置重复入队或前驱被覆盖。
- 只能扩展上下左右四个方向，不允许斜向跨过障碍。
- 回溯结果需要反转，并保留起点和终点；不可达与零步可达不能混淆。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1091. 二进制矩阵中的最短路径 | 中等 | 本题改为四方向、指定起终点并输出坐标路径，不能沿用原题的八方向与仅返回长度。 |
| 542. 01 矩阵 | 中等 | 都利用首次到达确定无权最短距离；原题多源求距，本题单源并保存前驱恢复路线。 |