题目描述
给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
- 路径途经的所有单元格都的值都是 0 。
- 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
- 畅通路径的长度 是该路径途经的单元格总数。
解题思路
DFS和BFS都可以解决路径搜索的问题。但是若想知道一些关于“最近/最快/最少”之类问题的答案，往往采用 BFS 更加适合。因为DFS要多次遍历，搜索所有可能路径，标识做了之后还要取消，而DFS每个结点只访问一遍。
class Solution:def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:m,n=len(grid),len(grid[0])moves=[(-1,1),(-1,0),(-1,-1),(0,1),(0,-1),(1,1),(1,0),(1,-1)]if grid[0][0]:return -1import collectionsqueue=collections.deque()queue.append((0,0))min_path=1grid[0][0]=1while queue:t=len(queue)while t>0:x,y=queue.popleft()if x==m-1 and y==n-1:return min_pathfor move in moves:x1,y1=x+move[0],y+move[1]if 0<=x1<m and 0<=y1<n and grid[x1][y1]==0:queue.append((x1,y1))grid[x1][y1]=1t-=1min_path+=1return -1
可以发现这其实和二叉树的层次遍历差不多，区别就是二叉树搜索的是左右两个节点，而求最短路径是搜索上下左右八个方向的节点。那么求最短路径就类似于求二叉树的深度了（层数=路径长度）。