1091. 二进制矩阵中的最短路径

题目描述

给你一个 n x n 的二进制矩阵 grid，返回矩阵中 最短畅通路径 的长度。如果不存在这样的路径，返回 -1。

畅通路径要求：

路径从左上角单元格 (0, 0) 开始
路径到右下角单元格 (n - 1, n - 1) 结束
路径中的所有单元格都必须是 0
路径中相邻单元格在 8 个方向之一 上连通，也就是可以上下左右和四个对角方向移动

路径长度是路径经过的单元格总数。

示例 1

text

输入：grid = [[0,1],[1,0]]
输出：2

示例 2

text

输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
输出：4

示例 3

text

输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
输出：-1

约束

n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] 为 0 或 1

核心思路

这题本质上是在一个网格图里找：

从起点到终点的 最短路径长度
每一步可以走 8 个方向
只能走值为 0 的格子

只要看到这种关键词：

最短路径
每一步代价相同
无权图

第一反应就应该是：

BFS（广度优先搜索）

因为 BFS 是一层一层往外扩展的：

第一次到达某个点时
走的一定是最短步数

这题至少有两种常见做法：

解法一：普通 BFS（推荐）
解法二：A 搜索（进阶）*

解法一：普通 BFS

这是这题最标准、最推荐掌握的做法。

思路拆解

把矩阵里的每个 0 格子看成图里的一个节点。

如果两个 0 格子在 8 个方向上相邻，那么它们之间就有一条边。

于是问题就变成：

从 (0,0) 到 (n-1,n-1) 的最短路有多长？

BFS 的做法是：

从起点 (0,0) 开始入队
每次从队头取出一个格子
尝试往 8 个方向扩展
第一次到达终点时，当前路径长度就是最短答案

一开始要先判断什么？

如果：

起点 grid[0][0] === 1
或终点 grid[n - 1][n - 1] === 1

那么起点或终点根本不能走，答案直接是 -1。

还有一个特殊情况：

如果 n === 1
并且 grid[0][0] === 0

那起点就是终点，答案就是 1。

一步一步写出算法

第一步：定义 8 个方向

const directions = [
    [-1, -1], [-1, 0], [-1, 1],
    [0, -1],           [0, 1],
    [1, -1],  [1, 0],  [1, 1],
]

第二步：准备队列和访问标记

我们把 (row, col, distance) 放进队列里。

也可以只存坐标，再按层统计距离；这里为了直观，直接把距离一起存进去。

const queue: [number, number, number][] = [0, 0, 1](<0, 0, 1.md>)

访问过的格子不能重复入队，否则会无限绕圈。

最省空间的方式是：

直接把访问过的 0 改成 1

grid[0][0] = 1

第三步：不断从队列取点扩展

while (queue.length > 0) {
    const [row, col, distance] = queue.shift()!
    ...
}

第四步：如果到达终点，直接返回

if (row === n - 1 && col === n - 1) {
    return distance
}

第五步：枚举 8 个方向

对于每个方向，算出新位置：

const nextRow = row + dx
const nextCol = col + dy

只要满足：

没越界
还是 0

就可以入队，并标记访问。

if (
    nextRow >= 0 && nextRow < n &&
    nextCol >= 0 && nextCol < n &&
    grid[nextRow][nextCol] === 0
) {
    grid[nextRow][nextCol] = 1
    queue.push([nextRow, nextCol, distance + 1])
}

第六步：如果 BFS 结束还没到终点

说明不可达，返回：

return -1

代码实现（TypeScript）

function shortestPathBinaryMatrix(grid: number[][]): number {
    const n = grid.length

    if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) {
        return -1
    }

    if (n === 1) {
        return 1
    }

    const directions = [
        [-1, -1], [-1, 0], [-1, 1],
        [0, -1],           [0, 1],
        [1, -1],  [1, 0],  [1, 1],
    ]

    const queue: [number, number, number][] = [0, 0, 1](<0, 0, 1.md>)
    grid[0][0] = 1

    while (queue.length > 0) {
        const [row, col, distance] = queue.shift()!

        if (row === n - 1 && col === n - 1) {
            return distance
        }

        for (const [dx, dy] of directions) {
            const nextRow = row + dx
            const nextCol = col + dy

            if (
                nextRow >= 0 && nextRow < n &&
                nextCol >= 0 && nextCol < n &&
                grid[nextRow][nextCol] === 0
            ) {
                grid[nextRow][nextCol] = 1
                queue.push([nextRow, nextCol, distance + 1])
            }
        }
    }

    return -1
}

复杂度分析

时间复杂度：O(n^2)
空间复杂度：O(n^2)

因为每个格子最多只会入队一次。

这一解法的优缺点

优点：

最直观
最容易写对
是标准解法

缺点：

队列如果直接用 shift()，在 JS / TS 里常数稍大
不是最“搜索优化”的写法

解法二：A* 搜索

这个做法更偏进阶，适合理解“如何更聪明地朝终点搜索”。

思路拆解

普通 BFS 会把所有可能的方向一层一层都扩出去。

而 A* 会优先扩展：

当前距离已经比较短
并且看起来离终点也更近

的节点。

A* 的核心是一个估价函数：

text

f(x) = g(x) + h(x)

其中：

g(x)：从起点到当前点已经走了多少步
h(x)：从当前点到终点还“至少”要多少步

因为这题允许走 8 个方向，所以从 (row, col) 到终点 (n-1, n-1) 的一个自然估价是：

max(abs(row - targetRow), abs(col - targetCol))

这其实就是“切比雪夫距离”。

为什么它适合这题？

因为：

一次斜着走，可以同时让行差和列差各减少 1
所以最少还要走多少步，确实就是两者差值中的较大者

A* 会优先弹出 f 值更小的点。

一步一步写出算法

第一步：仍然先处理边界情况

和 BFS 一样：

起点或终点是 1，直接返回 -1
n === 1 时返回 1

第二步：定义估价函数

const heuristic = (row: number, col: number): number => {
    return Math.max(Math.abs(n - 1 - row), Math.abs(n - 1 - col))
}

第三步：准备最小堆

堆里存：

f：总估价
g：当前真实路径长度
row
col

每次优先弹出 f 最小的状态。

第四步：用 `dist` 记录到每个点的最短已知距离

如果后来找到一条更差的路径到同一个点，就不用再处理。

第五步：不断弹出堆顶扩展

如果已经到终点，返回 g
否则尝试更新 8 个方向的邻居

代码实现（TypeScript）

class MinHeap {
    private data: [number, number, number, number][] = []

    push(value: [number, number, number, number]): void {
        this.data.push(value)
        this.bubbleUp(this.data.length - 1)
    }

    pop(): [number, number, number, number] | undefined {
        if (this.data.length === 0) {
            return undefined
        }

        const top = this.data[0]
        const last = this.data.pop()!
        if (this.data.length > 0) {
            this.data[0] = last
            this.bubbleDown(0)
        }
        return top
    }

    get size(): number {
        return this.data.length
    }

    private bubbleUp(index: number): void {
        while (index > 0) {
            const parent = Math.floor((index - 1) / 2)
            if (this.data[parent][0] <= this.data[index][0]) {
                break
            }
            ;[this.data[parent], this.data[index]] = [this.data[index], this.data[parent]]
            index = parent
        }
    }

    private bubbleDown(index: number): void {
        const n = this.data.length
        while (true) {
            let smallest = index
            const left = index * 2 + 1
            const right = index * 2 + 2

            if (left < n && this.data[left][0] < this.data[smallest][0]) {
                smallest = left
            }
            if (right < n && this.data[right][0] < this.data[smallest][0]) {
                smallest = right
            }
            if (smallest === index) {
                break
            }
            ;[this.data[smallest], this.data[index]] = [this.data[index], this.data[smallest]]
            index = smallest
        }
    }
}

function shortestPathBinaryMatrix(grid: number[][]): number {
    const n = grid.length

    if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) {
        return -1
    }

    if (n === 1) {
        return 1
    }

    const directions = [
        [-1, -1], [-1, 0], [-1, 1],
        [0, -1],           [0, 1],
        [1, -1],  [1, 0],  [1, 1],
    ]

    const heuristic = (row: number, col: number): number => {
        return Math.max(Math.abs(n - 1 - row), Math.abs(n - 1 - col))
    }

    const dist = Array.from({ length: n }, () => new Array(n).fill(Infinity))
    dist[0][0] = 1

    const heap = new MinHeap()
    heap.push([1 + heuristic(0, 0), 1, 0, 0])

    while (heap.size > 0) {
        const [_, steps, row, col] = heap.pop()!

        if (row === n - 1 && col === n - 1) {
            return steps
        }

        if (steps > dist[row][col]) {
            continue
        }

        for (const [dx, dy] of directions) {
            const nextRow = row + dx
            const nextCol = col + dy

            if (
                nextRow < 0 || nextRow >= n ||
                nextCol < 0 || nextCol >= n ||
                grid[nextRow][nextCol] === 1
            ) {
                continue
            }

            const nextSteps = steps + 1
            if (nextSteps < dist[nextRow][nextCol]) {
                dist[nextRow][nextCol] = nextSteps
                heap.push([
                    nextSteps + heuristic(nextRow, nextCol),
                    nextSteps,
                    nextRow,
                    nextCol,
                ])
            }
        }
    }

    return -1
}

复杂度分析

最坏情况下，仍然可能访问很多格子
时间复杂度可近似看成：O(n^2 log n)
空间复杂度：O(n^2)

它不一定比 BFS 的理论复杂度更好，但在一些数据下会更快到达终点。

这一解法的优缺点

优点：

更有“朝目标搜索”的感觉
是经典最短路启发式搜索方法

缺点：

代码明显更复杂
这题其实 BFS 已经足够好

两种解法对比

解法	时间复杂度	空间复杂度	特点
普通 BFS	`O(n^2)`	`O(n^2)`	最标准，最推荐
A* 搜索	近似 `O(n^2 log n)`	`O(n^2)`	更进阶，写法更复杂

如果你是第一次做这题，建议一定先彻底掌握 BFS。

手动模拟一遍 BFS

以：

text

grid = [[0,0,0],[1,1,0],[1,1,0]]

为例。

终点是：

text

(2, 2)

第一步：从 `(0,0)` 出发

路径长度记为 1。

当前队列：

text

[(0,0,1)]

第二步：扩展 `(0,0)`

它能走到的 0 邻居有：

(0,1)

所以入队：

text

[(0,1,2)]

第三步：扩展 `(0,1)`

它能走到的 0 邻居有：

(0,2)
(1,2)

队列变成：

text

[(0,2,3), (1,2,3)]

第四步：继续扩展

从 (1,2) 可以走到：

(2,2)

于是终点第一次被到达时，路径长度是：

text

这就是最短路径长度。

面试时最容易错的点

1. 这题可以走 8 个方向

不是只有上下左右。

所以方向数组一定要包含：

四个正方向
四个对角方向

2. 路径长度是“经过的格子数”

不是“移动次数”。

所以起点 (0,0) 本身的距离应该记成：

text

而不是 0。

3. 起点和终点都必须先检查

如果：

grid[0][0] === 1
或 grid[n - 1][n - 1] === 1

那答案直接就是 -1。

4. 访问标记一定要及时做

只要某个点准备入队，就应该立即标记已访问。

否则可能会被重复入队很多次。

5. BFS 第一次到终点就是最短路

因为每一步代价都一样，所以 BFS 层数天然对应最短路径长度。

一句话总结

这题的本质是：

在一个允许 8 方向移动的二进制网格里，求从左上角到右下角的最短路。

想写标准解：用 BFS
想学搜索优化：用 A 搜索*

1091. 二进制矩阵中的最短路径

题目描述

示例 1

示例 2

示例 3

约束

核心思路

解法一：普通 BFS

思路拆解

一开始要先判断什么？

一步一步写出算法

第一步：定义 8 个方向

第二步：准备队列和访问标记

第三步：不断从队列取点扩展

第四步：如果到达终点，直接返回

第五步：枚举 8 个方向

第六步：如果 BFS 结束还没到终点

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

解法二：A* 搜索

思路拆解

一步一步写出算法

第一步：仍然先处理边界情况

第二步：定义估价函数

第三步：准备最小堆

第四步：用 dist 记录到每个点的最短已知距离

第五步：不断弹出堆顶扩展

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

两种解法对比

手动模拟一遍 BFS

第一步：从 (0,0) 出发

第二步：扩展 (0,0)

第三步：扩展 (0,1)

第四步：继续扩展

面试时最容易错的点

1. 这题可以走 8 个方向

2. 路径长度是“经过的格子数”

3. 起点和终点都必须先检查

4. 访问标记一定要及时做

5. BFS 第一次到终点就是最短路

一句话总结

推荐你最后记住的标准写法

第四步：用 `dist` 记录到每个点的最短已知距离

第一步：从 `(0,0)` 出发

第二步：扩展 `(0,0)`

第三步：扩展 `(0,1)`