二进制矩阵中寻找最短畅通路径 - BFS算法详解

二进制矩阵中寻找最短畅通路径 - BFS算法详解

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

在二进制矩阵中，畅通路径指的是一条从左上角单元格（即，(0, 0)）到右下角单元格（即，(n - 1, n - 1)）的路径，该路径满足以下要求：

1. 路径途经的所有单元格的值都是 0。
2. 路径中所有相邻的单元格应当在 8 个方向之一上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度是指该路径途经的单元格总数。

解题思路

本题可以使用广度优先搜索（BFS）来解决。从起点 (0, 0) 开始，每次将所有相邻且值为 0 的格子加入队列中，继续进行 BFS。当到达终点 (n-1, n-1) 时，返回路径长度即可。如果无法到达终点，则返回 -1。

需要注意的是，为了避免重复访问某个格子，需要在访问过的格子上标记一个已访问的标记，可以使用一个与原矩阵大小相同的 visited 数组来记录。

具体实现时，可以将每个格子的坐标和当前路径长度打包成一个元组，作为 BFS 队列中的元素。同时，可以在 BFS 过程中记录当前已访问的格子数，如果已访问的格子数等于矩阵大小，则说明已经找到了一条从起点到终点的路径，可以提前结束 BFS。

时间复杂度和空间复杂度

• 时间复杂度：O(n^2)，其中 n 是矩阵的大小。最坏情况下，需要遍历所有格子。
• 空间复杂度：O(n^2)，其中 n 是矩阵的大小。需要使用 visited 数组记录已访问的格子。