跳到主要内容

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

本节目标

用八方向网格 BFS 求从左上角到右下角经过格子的最少数量。

这道题是网格与状态图搜索中的最短路版本：开放格是状态，八个方向是邻接关系，路径长度按经过的格子数计。

查看 LeetCode 原题

朴素思路与瓶颈​

枚举从左上到右下的所有简单路径会产生指数级分支，并且必须比较所有候选长度。由于每次移动只跨一条等权边，BFS 天然按路径长度递增；第一次取到终点时就是最短答案。

八方向 BFS 不变量​

起点或终点被阻塞时没有路径，先返回 -1。否则从 (0, 0, 1) 入队，1 表示起点本身已计入长度。每次扩展八个方向，越界、障碍和已访问格都跳过。

本实现把入队的开放格改为非零，作为访问标记。标记发生在入队前，所以没有格子会由不同方向重复进入队列。单格开放矩阵的起点同时是终点，返回 1。

原地修改​

搜索会把已经入队的 0 改为 1。这不会改变最短路径结论，却让网格同时承担障碍和访问集合的职责；若调用者必须保留原矩阵，可改用同尺寸 visited 矩阵。

代码实现​

C++17 与 Python 3 均通过 shortestPathBinaryMatrix 接收网格，不读取输入流。队列保存坐标及当前路径长度，源码中的访问标记严格发生在入队阶段。

C++17
#include <array>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int size = static_cast<int>(grid.size());
        if (grid[0][0] != 0 || grid[size - 1][size - 1] != 0) {
            return -1;
        }

        const array<pair<int, int>, 8> directions{{
            {-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
            {0, 1}, {1, -1}, {1, 0}, {1, 1},
        }};
        queue<array<int, 3>> states;
        states.push({0, 0, 1});
        grid[0][0] = 1;

        while (!states.empty()) {
            array<int, 3> current = states.front();
            states.pop();
            int row = current[0];
            int col = current[1];
            int distance = current[2];
            if (row == size - 1 && col == size - 1) {
                return distance;
            }

            for (const auto& [rowChange, colChange] : directions) {
                int nextRow = row + rowChange;
                int nextCol = col + colChange;
                if (nextRow < 0 || nextRow >= size || nextCol < 0 || nextCol >= size) {
                    continue;
                }
                if (grid[nextRow][nextCol] != 0) {
                    continue;
                }

                // 网格改为非零即访问，随后才入队。
                grid[nextRow][nextCol] = 1;
                states.push({nextRow, nextCol, distance + 1});
            }
        }

        return -1;
    }
};

复杂度分析​

设矩阵边长为 n。每个格子至多入队一次，八个方向为常数，时间复杂度为 O(n²)；队列最坏保存 O(n²) 个格子，空间复杂度为 O(n²)。

易错点​

  • 把路径长度初始化为 0，使单格开放矩阵得到错误答案。
  • 漏掉四个对角方向，无法通过只能斜向连通的矩阵。
  • 起点或终点为 1 时仍然开始 BFS。
  • 直到出队才标记，导致相邻格在同层重复入队。

模式迁移​

迷宫最少步数、最近出口和带障碍的棋盘移动都可复用此模型。变化通常只在方向集合、起终点定义和距离是否从格子数或边数起算；BFS 的层序与入队标记规则保持不变。