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

题目描述：给定一个 n x n 的二进制矩阵 grid，返回从左上角 (0, 0) 到右下角 (n-1, n-1) 的最短畅通路径的长度。如果不存在这样的路径，返回 -1。

二进制矩阵中的畅通路径是指从左上角到右下角、只包含 0 的路径（不允许走到值为 1 的格子）。路径可以向上、下、左、右、左上、右上、左下、右下八个方向移动（如果存在）。

解题过程：

1. 问题分析

• 这是一个在网格图中寻找最短路径的问题
• 与常规的四方向移动不同，这里允许八方向移动
• 网格中有障碍物（值为1的格子）
• 需要找到从起点到终点的最短路径长度

2. 算法选择

• 由于是寻找最短路径，且所有边的权重相同（每步代价为1），适合使用广度优先搜索（BFS）
• BFS保证第一次到达终点时走过的路径就是最短路径
• 深度优先搜索（DFS）不适合，因为它不能保证找到的路径是最短的

3. 详细步骤
   步骤1：特殊情况处理

• 如果起点或终点是障碍物（值为1），直接返回-1
• 如果矩阵只有1x1大小，起点就是终点，返回0（不需要移动）

步骤2：BFS初始化

• 创建队列存储待访问的坐标和步数
• 创建visited矩阵记录已访问的格子，避免重复访问
• 定义八个移动方向：上、下、左、右、四个对角线方向

步骤3：BFS执行过程

• 将起点(0,0)加入队列，步数为1（起点算第一步）
• 标记起点为已访问
• 循环处理队列直到为空或找到终点：
  • 取出当前格子坐标和步数
  • 如果当前格子是终点，返回步数
  • 否则，向八个方向探索：
    • 计算新坐标
    • 检查新坐标是否越界
    • 检查新格子是否为0且未被访问
    • 如果满足条件，加入队列并标记为已访问

步骤4：队列处理完毕仍未找到终点，返回-1

4. 关键要点

• 使用BFS而不是DFS，因为BFS按层扩展，保证最短路径
• 八个方向的移动使得路径可能更短，但搜索空间更大
• 必须记录已访问的格子，避免无限循环
• 步数计算：起点算第1步，每移动一步步数加1

5. 复杂度分析

• 时间复杂度：O(n²)，每个格子最多访问一次
• 空间复杂度：O(n²)，用于队列和visited矩阵

这个算法能有效找到最短路径，因为BFS的特性保证了第一次到达终点时经过的路径就是最短的。