LC1091Medium网格BFS八方向无权最短路

二进制矩阵中的最短路径

把每个可走的 0 当作无权图节点，八个方向都是一步。BFS 按距离一圈圈扩散，第一次到达右下角就是最短路径。

题目是什么

从左上角走到右下角，只能经过 0，允许八方向移动，求最短路径长度。

解决什么问题

在无权网格中保证找到全局最短路径，而不是随便找到一条可行路径。

核心结论

起点距离为 1；八方向 BFS，入队立即标记；首次到达终点即返回距离。

01交互算法精讲

先说结论：这道题到底解决什么

路线数量可能指数增长时，为什么从起点按距离一圈圈扩散，就能在第一次到达右下角时确定全局最短路径？

中心结论：起点距离为 1；八方向 BFS，入队立即标记；首次到达终点即返回距离。

读完必须能回答

1.为什么这题必须检查八个方向，而且起点距离从 1 开始？
2.为什么格子应该在入队时立即标记，而不是出队时再标记？
3.为什么 BFS 第一次弹出终点时，不可能还存在更短路线？

02交互算法精讲

完整题目与题意拆解

给定 n×n 二进制矩阵 grid，从左上角 (0,0) 走到右下角 (n-1,n-1)。只有值为 0 的格子可以经过。

每一步可以移动到八个相邻方向，包括水平、垂直和对角线。路径长度是经过的单元格数量；不存在路径时返回 -1。

• 对角线相邻也只算一步。
• 起点和终点都必须是 0。
• n=1 且唯一格为 0 时，路径长度为 1。

输入：grid = [[0,1,0],[0,0,0],[1,0,0]]
输出：3
最短路径：(0,0) → (1,1) → (2,2)。

每个可走格是一个图节点，两个八方向相邻的可走格之间有一条长度为 1 的边。这就是标准无权最短路。

路径长度数格子，因此起点已经贡献 1。之后每扩展一层，所有新节点的距离都比上一层多 1。

主例可以从 (0,0) 斜走到 (1,1)，再斜走到 (2,2)，共经过 3 个格子；只写四方向会错过这条答案。

动画 1 · 题意扫描

先确认八方向与距离定义

观察起终点、墙和八个方向；特别留意斜走一步与起点距离为 1。

Step 1/30%

0 可走 · 1 阻塞 · 八方向

0start

0end

start=(0,0) · end=(2,2)

这张地图允许八方向移动

发生了什么: 起点是 (0,0)，终点是 (2,2)，值为 1 的格子是墙。
为什么: 对角线也只花一步，决定了邻居集合与普通四方向网格不同。
下一步: 先用常数时间检查起点和终点是否被墙堵住。

当前状态

directions

当前 Go 代码

1func shortestPathBinaryMatrix(grid [][]int) int {2    n := len(grid)3    if grid[0][0] != 0 || grid[n-1][n-1] != 0 { return -1 }4    dirs := [][2]int{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}5    queue := [][3]int{{0, 0, 1}}6    grid[0][0] = 17    for len(queue) > 0 {8        cur := queue[0]; queue = queue[1:]9        if cur[0] == n-1 && cur[1] == n-1 {10            return cur[2]11        }12        for _, d := range dirs { nr, nc := cur[0]+d[0], cur[1]+d[1]13            if nr<0 || nr>=n || nc<0 || nc>=n || grid[nr][nc]!=0 { continue }14            grid[nr][nc] = 115            queue = append(queue, [3]int{nr,nc,cur[2]+1})16        }17    }18    return -119}

看完带走：对角线也是一条单位边，路径长度统计经过的格子数量。

03交互算法精讲

第一层方案：暴力做法

可以用 DFS 回溯枚举从起点到终点的所有可行路径，维护 visited，抵达终点后更新最小长度。

网格上可能存在大量路线，同一片区域会被不同路径反复探索。即使剪枝，证明和实现都比 BFS 更复杂。

dfs(r,c,length)
  尝试八个方向
  到终点时 answer=min(answer,length)

只要每条边代价相同，BFS 就能用访问层次直接给出最短距离，不必枚举完整路径集合。

动画 2 · 暴力重复

DFS 第一条路线为什么不保证最短

对照普通路线展开与 BFS 距离顺序，观察先深入一条路可能绕远，而波前会先覆盖所有短路线。

Step 1/30%

距离 1 的波前

0start

0end

neighbors → (1,0), (1,1)

第一圈同时检查八个方向

发生了什么: 从 (0,0) 出发，越界与墙被跳过，可走的 (1,0)、(1,1) 被发现。
为什么: 方向数组统一表达横、竖、斜移动，避免漏掉对角线。
下一步: 把两个新格以距离 2 入队。

当前状态

current

(0,0,d=1)

当前 Go 代码

1func shortestPathBinaryMatrix(grid [][]int) int {2    n := len(grid)3    if grid[0][0] != 0 || grid[n-1][n-1] != 0 { return -1 }4    dirs := [][2]int{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}5    queue := [][3]int{{0, 0, 1}}6    grid[0][0] = 17    for len(queue) > 0 {8        cur := queue[0]; queue = queue[1:]9        if cur[0] == n-1 && cur[1] == n-1 {10            return cur[2]11        }12        for _, d := range dirs { nr, nc := cur[0]+d[0], cur[1]+d[1]13            if nr<0 || nr>=n || nc<0 || nc>=n || grid[nr][nc]!=0 { continue }14            grid[nr][nc] = 115            queue = append(queue, [3]int{nr,nc,cur[2]+1})16        }17    }18    return -119}

看完带走：最短保证来自队列的距离顺序，不来自“先碰巧走到终点”。

优化方向：BFS 的队列保证距离小的状态先出队。第一次发现一个格子时，就已经得到它的最短距离，不需要重新放入更长路线。

04交互算法精讲

整体地图：先做什么，再做什么

先把每个值为 0 的格子看成无权图节点，八方向可达关系看成代价为 1 的边。起点或终点阻塞时直接失败，否则把起点以距离 1 放入队列。

BFS 每次弹出当前最短距离的格子，检查八个邻居。合法且未访问的格子以 distance+1 入队并立即标记；第一次弹出终点就返回距离。

• 建模：0 是节点，八方向是等权边。
• 搜索：队列保证距离非递减。
• 终止：弹出终点返回，队列耗尽返回 -1。

这题不要求恢复路径，只要求长度，所以队列状态只需保存 row、col、distance。

05交互算法精讲

BFS 波前到底保存了什么

队列不是随意的待办列表。起点距离为 1；从距离 d 的格子发现的邻居全部记录为 d+1，因此队列中的距离始终非递减。

同一圈波前中的格子都拥有相同或相邻的距离。算法会处理完所有更短候选后，才可能弹出更长候选，这正是最短路保证的来源。

(0,0,1) → 第一圈邻居 distance=2 → 第二圈邻居 distance=3
主例最短路线：(0,0) → (1,1) → (2,2)，经过 3 个格子

路径长度按经过的格子数计算，不是边数；因此单格 `[[0]]` 的答案是 1。

动画 3 · 核心概念

距离 1、2、3 的波前依次扩散

观察起点、对角格和终点如何分别落在连续三层中。

Step 1/40%

BFS 初始化

0d=1

0end

queue

(0,0,d=1)

distance(start)=1

起点距离从 1 开始

发生了什么: 将 (0,0,1) 入队，并立即把起点标记为已访问。
为什么: 路径长度统计经过的格子，起点本身已经是第一个格子。
下一步: 弹出距离 1 的起点并检查八个邻居。

当前状态

distance

当前 Go 代码

1func shortestPathBinaryMatrix(grid [][]int) int {2    n := len(grid)3    if grid[0][0] != 0 || grid[n-1][n-1] != 0 { return -1 }4    dirs := [][2]int{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}5    queue := [][3]int{{0, 0, 1}}6    grid[0][0] = 17    for len(queue) > 0 {8        cur := queue[0]; queue = queue[1:]9        if cur[0] == n-1 && cur[1] == n-1 {10            return cur[2]11        }12        for _, d := range dirs { nr, nc := cur[0]+d[0], cur[1]+d[1]13            if nr<0 || nr>=n || nc<0 || nc>=n || grid[nr][nc]!=0 { continue }14            grid[nr][nc] = 115            queue = append(queue, [3]int{nr,nc,cur[2]+1})16        }17    }18    return -119}

看完带走：每个新格的距离只比父格大 1，所以队列不会越过更短层。

06交互算法精讲

如何展开八方向并避免重复排队

每个出队格检查八个方向偏移。越界、值为 1 的墙、已经访问的格子都跳过。合法邻居一经发现就把 grid 改成 1，并携带 distance+1 入队。

立即标记的原因是第一次发现已经给出了该格子的最短距离。若等到出队才标记，同一层的多个父格会把它重复加入队列，虽然可能仍正确，却会浪费大量时间和空间。

• 起终点阻塞先返回 -1。
• 八方向包含横、竖和四条对角线。
• 终点判断放在出队后，返回当前携带的 distance。

队列元素保存行、列、距离。八方向可写成包含 (-1,-1) 到 (1,1) 且排除 (0,0) 的固定数组。

处理邻居时先判边界，再要求 grid[nr][nc]==0。入队前把该格改为 1，复用原矩阵作为 visited。

出队才标记会让同一格被多个父节点重复加入队列；首次发现已经是最短，应在入队时立即锁定。

动画 4 · 机制构建

八方向检查与入队标记同步

逐步观察合法性检查、对角邻居入队以及为什么第一次发现就立刻标记。

Step 1/30%

距离 1 的波前

0start

0end

neighbors → (1,0), (1,1)

第一圈同时检查八个方向

发生了什么: 从 (0,0) 出发，越界与墙被跳过，可走的 (1,0)、(1,1) 被发现。
为什么: 方向数组统一表达横、竖、斜移动，避免漏掉对角线。
下一步: 把两个新格以距离 2 入队。

当前状态

current

(0,0,d=1)

当前 Go 代码

1func shortestPathBinaryMatrix(grid [][]int) int {2    n := len(grid)3    if grid[0][0] != 0 || grid[n-1][n-1] != 0 { return -1 }4    dirs := [][2]int{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}5    queue := [][3]int{{0, 0, 1}}6    grid[0][0] = 17    for len(queue) > 0 {8        cur := queue[0]; queue = queue[1:]9        if cur[0] == n-1 && cur[1] == n-1 {10            return cur[2]11        }12        for _, d := range dirs { nr, nc := cur[0]+d[0], cur[1]+d[1]13            if nr<0 || nr>=n || nc<0 || nc>=n || grid[nr][nc]!=0 { continue }14            grid[nr][nc] = 115            queue = append(queue, [3]int{nr,nc,cur[2]+1})16        }17    }18    return -119}

看完带走：入队立即标记能阻止同层多个父格重复安排同一个状态。

07交互算法精讲

核心难点：为什么第一次到达一定最短

所有移动代价都为 1。BFS 从距离 1 的起点开始，只会从距离 d 生成距离 d+1，因此队列弹出顺序按距离非递减。

假设第一次弹出终点时距离为 D，却存在更短路线 D-1。那条路线的倒数第二个格子距离至多 D-2，必然在终点之前已经出队，并会把终点以更短距离加入队列，与“第一次弹出距离 D”矛盾。

入队立即标记不会漏掉更短路线，因为第一次发现某格时，所有更短层已经处理；后来从同层或更长层再次到达只可能得到相同或更长距离。

DFS 找到第一条路径不具备这个距离顺序，因此不能在第一次到达时保证最短。

正确性抓手

• 队列按距离非递减顺序弹出节点，所有边代价都为 1。
• 第一次发现节点就是其最短距离，入队标记不会丢失更短路线。
• 因此第一次弹出终点时，不可能还有尚未处理的更短终点路线。

08交互算法精讲

完整执行过程

观察距离 1、2、3 的波前，以及对角线如何把路径缩短。每个新格在入队时立即变成已访问状态。

1检查左上角和右下角都为 0；将起点 (0,0) 以 distance=1 入队并标记。
2弹出起点，检查八方向；墙和越界跳过，对角格 (1,1) 以 distance=2 入队。
3由于入队时已经标记，其他格子不会把 (1,1) 重复放入队列。
4弹出 (1,1)，从八方向发现终点 (2,2)，记录 distance=3。
5终点按距离顺序弹出时返回 3；若队列耗尽仍未弹出终点则返回 -1。

动画 5 · 完整执行

从左上角完整走到右下角

播放端点检查、起点入队、两圈扩散、终点返回和复杂度收束。

Step 1/90%

0 可走 · 1 阻塞 · 八方向

0start

0end

start=(0,0) · end=(2,2)

这张地图允许八方向移动

发生了什么: 起点是 (0,0)，终点是 (2,2)，值为 1 的格子是墙。
为什么: 对角线也只花一步，决定了邻居集合与普通四方向网格不同。
下一步: 先用常数时间检查起点和终点是否被墙堵住。

当前状态

directions

当前 Go 代码

1func shortestPathBinaryMatrix(grid [][]int) int {2    n := len(grid)3    if grid[0][0] != 0 || grid[n-1][n-1] != 0 { return -1 }4    dirs := [][2]int{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}5    queue := [][3]int{{0, 0, 1}}6    grid[0][0] = 17    for len(queue) > 0 {8        cur := queue[0]; queue = queue[1:]9        if cur[0] == n-1 && cur[1] == n-1 {10            return cur[2]11        }12        for _, d := range dirs { nr, nc := cur[0]+d[0], cur[1]+d[1]13            if nr<0 || nr>=n || nc<0 || nc>=n || grid[nr][nc]!=0 { continue }14            grid[nr][nc] = 115            queue = append(queue, [3]int{nr,nc,cur[2]+1})16        }17    }18    return -119}

看完带走：第一次弹出终点时，队列里不可能还藏着一条更短路线。

09交互算法精讲

把动画和 Go 代码逐行对应

每一帧使用稳定的语义行 ID，不依赖容易漂移的数字行号。先观察分支为什么成立，再看对应代码，而不是先背模板。

动画 6 · 代码映射

从阻塞检查到终点返回逐行对应

观察每个画面状态对应的 Go 分支：初始化、出队、终点判断、八邻居、标记与入队。

Step 1/50%

端点检查通过

0start

0end

grid[0][0]==0 && grid[2][2]==0

任一端阻塞就立刻失败

发生了什么: 主例起点和终点都是 0，可以继续搜索。
为什么: 所有合法路径必须包含这两个端点，任一为 1 都不存在答案。
下一步: 把起点以距离 1 放入队列。

当前状态

blocked

false

当前 Go 代码

1func shortestPathBinaryMatrix(grid [][]int) int {2    n := len(grid)3    if grid[0][0] != 0 || grid[n-1][n-1] != 0 { return -1 }4    dirs := [][2]int{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}5    queue := [][3]int{{0, 0, 1}}6    grid[0][0] = 17    for len(queue) > 0 {8        cur := queue[0]; queue = queue[1:]9        if cur[0] == n-1 && cur[1] == n-1 {10            return cur[2]11        }12        for _, d := range dirs { nr, nc := cur[0]+d[0], cur[1]+d[1]13            if nr<0 || nr>=n || nc<0 || nc>=n || grid[nr][nc]!=0 { continue }14            grid[nr][nc] = 115            queue = append(queue, [3]int{nr,nc,cur[2]+1})16        }17    }18    return -119}

看完带走：代码行顺序保证每个格子只以最短距离进入队列一次。

Step 1

这张地图允许八方向移动

对角线也只花一步，决定了邻居集合与普通四方向网格不同。

func · blocked-check

Step 2

任一端阻塞就立刻失败

所有合法路径必须包含这两个端点，任一为 1 都不存在答案。

blocked-check · queue-init

Step 3

起点距离从 1 开始

路径长度统计经过的格子，起点本身已经是第一个格子。

queue-init · mark-start · while

Step 4

第一圈同时检查八个方向

方向数组统一表达横、竖、斜移动，避免漏掉对角线。

pop · direction-loop · skip-invalid

Step 5

对角线 (1,1) 也是一步

从 (0,0) 到对角格只经过一次移动，不能按曼哈顿距离计算。

direction-loop · mark-neighbor · enqueue-neighbor

Step 6

第一次发现时立即标记

BFS 第一次发现已经给出最短距离，重复队列项只会浪费时间和空间。

mark-neighbor · enqueue-neighbor

Step 7

第二圈发现终点，路径长度为 3

新节点距离等于父节点距离加一，路径经过三个格子。

enqueue-neighbor · end-check · return-distance

Step 8

为什么第一次到达一定最短

所有边权都为 1，BFS 不可能在遗漏更短状态时提前弹出更长状态。

while · pop · end-check

Step 9

最多处理 n² 个格子

每个格子入队时立即标记，所以最多入队一次；n=1 的开放起点会直接返回 1。

while · return-failure

10交互算法精讲

完整 Go 提交代码与最小测试

完整 Go 解法

1func shortestPathBinaryMatrix(grid [][]int) int {2    n := len(grid)3    if grid[0][0] != 0 || grid[n-1][n-1] != 0 { return -1 }4    dirs := [][2]int{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}5    queue := [][3]int{{0, 0, 1}}6    grid[0][0] = 17    for len(queue) > 0 {8        cur := queue[0]; queue = queue[1:]9        if cur[0] == n-1 && cur[1] == n-1 {10            return cur[2]11        }12        for _, d := range dirs { nr, nc := cur[0]+d[0], cur[1]+d[1]13            if nr<0 || nr>=n || nc<0 || nc>=n || grid[nr][nc]!=0 { continue }14            grid[nr][nc] = 115            queue = append(queue, [3]int{nr,nc,cur[2]+1})16        }17    }18    return -119}

最小测试集合

// 主例：允许对角移动
shortestPathBinaryMatrix([][]int{{0,1,0},{0,0,0},{1,0,0}}) // 3

// 起点阻塞
shortestPathBinaryMatrix([][]int{{1,0},{0,0}}) // -1

// 终点阻塞
shortestPathBinaryMatrix([][]int{{0,0},{0,1}}) // -1

// 单个开放格，路径长度按格子数
shortestPathBinaryMatrix([][]int{{0}}) // 1

// 没有任何可达路线
shortestPathBinaryMatrix([][]int{{0,1,1},{1,1,1},{1,1,0}}) // -1

11交互算法精讲

正确性与复杂度

时间复杂度 O(n²)

n×n 网格中的每个可走格最多入队和出队一次，每次检查固定八个方向。

空间复杂度 O(n²)

最坏情况下 visited 标记复用原矩阵，但 BFS 队列仍可能保存 O(n²) 个格子。

12交互算法精讲

最容易写错的地方

错误 1

只写上下左右四个方向，漏掉对角线。

错误 2

把起点距离设为 0，导致答案少一。

错误 3

出队时才标记 visited，造成大量重复入队。

错误 4

用 DFS 找到第一条路径就直接返回。

13交互算法精讲

最后复盘：带走逻辑链

1.路径长度数格子，所以起点距离为 1。
2.八方向是本题区别于普通网格 BFS 的关键。
3.无权图 BFS 的首次到达保证最短。
4.迁移题：LC994 多源扩散、LC127 单词接龙。

面试表达

1.把每个 0 格看作无权图节点，八方向相邻就是边，使用 BFS 求最短路。
2.先判起点终点阻塞；起点以距离 1 入队并立即标记。
3.弹出后检查终点，再把合法未访问的八邻居以 distance+1 入队。
4.首次到达即最短；时间 O(n²)，最坏队列空间 O(n²)。