给你一个 n x n 的二进制矩阵 grid 中返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径返回 -1 。二进制矩阵中的 畅通路径 是一条从 左上角 单元格即0 0到 右下角 单元格即n - 1 n - 1的路径该路径同时满足下述要求：路径途经的所有单元格的值都是 0 。路径中所有相邻的单元格应当在 8 个方向之一 上连通即相邻两单元之间彼此不同且共享一条边或者一个角。畅通路径的长度 是
解法：BFS
可以使用 BFS 在矩阵中寻找最短路径。首先将起点 (0,0) 加入队列，然后不断从队列中取出第一个元素，向其相邻的 8 个方向扩展，并将扩展出的元素加入队列中。为了避免重复扩展同一个位置，我们可以将已经扩展过的位置标记为 1，表示不可再次访问。
时间复杂度：O(n^2) 空间复杂度：O(n^2)
Python 代码
原文地址: https://www.cveoy.top/t/topic/gdJI 著作权归作者所有。请勿转载和采集!