NOI 竞赛模拟题：二进制矩阵中的最短路径

题目描述

在一个 $n \times n$ 的二进制矩阵 grid 中，找出从左上角 $(0, 0)$ 到右下角 $(n-1, n-1)$ 的最短路径的长度。如果不存在这样的路径，返回 -1。

最短路径的定义：

1. 路径上的所有单元格的值都必须为 0。
2. 路径中相邻的单元格需在 8 个方向 上相邻（上、下、左、右、以及 4 条对角线方向）。
3. 路径长度是该路径中包含的单元格数目。

---

输入格式

第一行包含一个整数 $n$，表示矩阵的大小。 接下来 $n$ 行，每行包含 $n$ 个以空格分隔的整数（0 或 1）。

输出格式

输出一个整数，表示最短路径的长度。

---

输入输出样例

样例 1

输入：

2
0 1
1 0

输出：

2

样例 2

输入：

3
0 0 0
1 1 0
1 1 0

输出：

4

样例 3

输入：

3
1 0 0
1 1 0
1 1 0

输出：

-1

数据范围与提示

• $n = grid.length$
• $n = grid[i].length$
• $1 \le n \le 100$
• $grid[i][j]$ 为 0 或 1

---

1. 预备知识点

作为 NOI 选手，在解决此题前需要熟练掌握：

• 广度优先搜索 (BFS)：求解无权图/等权图最短路径问题的标准算法。
• 状态空间搜索：如何在网格图中定义状态及其迁移。
• 队列 (std::queue)：BFS 的核心数据结构。
• 方向数组：技巧性处理 8 个方向的偏移量。

---

2. 启发式思路引导（草稿纸上的思考过程）

第一步：观察搜索空间

我们在草稿纸上画一个 $3 \times 3$ 的格子。

• 每一个 (x, y) 是一个节点。
• 两个节点之间有边，当且仅当它们相邻（8方向）且值均为 0。
• 结论：这是一个求起点到终点的最少跳数问题，属于单源最短路。由于每条边的权重默认为 1，BFS 是最优选择。

第二步：特殊情况处理

• 起点 grid[0][0] 是 1 怎么办？（直接走不通）
• 终点 grid[n-1][n-1] 是 1 怎么办？（直接进不去）
• 矩阵大小 $n=1$ 且 $grid[0][0]=0$ 怎么办？（路径长为 1）

第三步：状态与转移

• 状态：(x, y, dist)，表示到达坐标 (x, y) 时的最短路径长度为 dist。
• 转移：从 (x, y) 出发，计算 nx = x + dx[i], ny = y + dy[i]。
• 条件判断：
  1. $0 \le nx < n$ 且 $0 \le ny < n$（不越界）。
  2. $grid[nx][ny] == 0$（可通行）。
  3. 未曾访问过该点（避免死循环，保证“最短”性质）。

第四步：复杂度分析

• 时间复杂度：每个单元格最多入队一次。总单元格数为 $N^2$，每个点检查 8 个方向。故时间复杂度为 $O(N^2)$。
• 空间复杂度：需要一个 $N \times N$ 的数组记录访问状态或距离，以及一个队列。故空间复杂度为 $O(N^2)$。

---

3. 算法逻辑流程图 (Mermaid)

graph TD
    A["开始: 检查起点/终点是否为 1"] --> B{"起点或终点为 1?"}
    B -- "是" --> C["返回 -1"]
    B -- "否" --> D["初始化队列 Q, 将 (0,0,1) 入队"]
    D --> E["标记 (0,0) 为已访问"]
    E --> F{"队列 Q 是否为空?"}
    F -- "是" --> G["未找到路径, 返回 -1"]
    F -- "否" --> H["弹出队首元素 (currX, currY, steps)"]
    H --> I{"是否到达终点 (n-1, n-1)?"}
    I -- "是" --> J["输出 steps, 结束"]
    I -- "否" --> K["遍历 8 个方向 (dx, dy)"]
    K --> L["计算新坐标 (nx, ny)"]
    L --> M{"(nx, ny) 有效且 grid 为 0 且未访问?"}
    M -- "是" --> N["标记已访问, 将 (nx, ny, steps+1) 入队"]
    M -- "否" --> K
    N --> K
    K -- "遍历完所有方向" --> F

---

4. 读题关键词与坑点总结

1. “最短路径”：在无权图中，看到此词应立即联想到 BFS。
2. “8 个方向”：这是最容易忽略的地方。普通走格子通常是 4 方向，这里包含对角线，方向数组 dx[], dy[] 应包含 8 组值。
3. “路径长度”：注意本题要求的是单元格数目。起点本身算 1 个长度，所以初始 dist 应为 1。
4. 边界条件：$N=1$ 的情况，以及起点即终点且为障碍的情况。

5. 复杂度优化建议

• 空间优化：可以直接在原 grid 数组上打标记（例如将 0 改为 1 或其他值），从而节省一个 visited 数组的空间。
• 双向 BFS：如果 $N$ 的范围进一步扩大（例如 $N=1000$），可以考虑从起点和终点同时开启 BFS，当两个搜索面相遇时即可得到最短路，这在状态空间巨大的题目中能显著减少搜索节点数。但在 $N=100$ 的情况下，普通 BFS 已足够优秀。