难度: Medium
给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
0 。畅通路径的长度 是该路径途经的单元格总数。
示例 1：
输入：grid = [[0,1],[1,0]] 输出：2
示例 2：
输入：grid = [[0,0,0],[1,1,0],[1,1,0]] 输出：4
示例 3：
输入：grid = [[1,0,0],[1,1,0],[1,1,0]] 输出：-1
提示：
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j] 为 0 或 1运行时间: 115 ms
内存: 16.6 MB
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
if grid[0][0] == 1:
return -1
q = [[0, 0]]
steps = 1
m = len(grid)
n = len(grid[0])
mark = [[False]*n for _ in range(m)]
mark[0][0] = True
while q:
temp = q
q = []
for i, j in temp:
if i == m-1 and j == n-1:
return steps
if i>0 and grid[i-1][j] == 0 and not mark[i-1][j]:
q.append([i-1, j])
mark[i-1][j] = True
if i<m-1 and grid[i+1][j] == 0 and not mark[i+1][j]:
q.append([i+1, j])
mark[i+1][j] = True
if j>0 and grid[i][j-1] == 0 and not mark[i][j-1]:
q.append([i, j-1])
mark[i][j-1] = True
if j<n-1 and grid[i][j+1] == 0 and not mark[i][j+1]:
q.append([i, j+1])
mark[i][j+1] = True
if i>0 and j>0 and grid[i-1][j-1] == 0 and not mark[i-1][j-1]:
q.append([i-1, j-1])
mark[i-1][j-1] = True
if i>0 and j<n-1 and grid[i-1][j+1] == 0 and not mark[i-1][j+1]:
q.append([i-1, j+1])
mark[i-1][j+1] = True
if i<m-1 and j>0 and grid[i+1][j-1] == 0 and not mark[i+1][j-1]:
q.append([i+1, j-1])
mark[i+1][j-1] = True
if i<m-1 and j<n-1 and grid[i+1][j+1] == 0 and not mark[i+1][j+1]:
q.append([i+1, j+1])
mark[i+1][j+1] = True
steps += 1
return -1
这个题解使用的是宽度优先搜索（BFS）算法来寻找从矩阵左上角到右下角的最短路径。首先，如果起点即grid[0][0]为1，则直接返回-1，因为起点不通畅。接着，使用一个队列q来存储需要探索的坐标，初始时只有起点[0, 0]。然后用一个二维数组mark来记录已经访问过的坐标，避免重复访问。接下来，进行BFS，每次从队列中取出一个坐标，检查它的8个方向上的相邻坐标，如果相邻坐标是0且未被访问过，则将其加入队列，并标记为已访问。当到达终点时，返回当前的步数。如果遍历完所有可达的坐标后仍未到达终点，则返回-1。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
if grid[0][0] == 1:
return -1
q = [[0, 0]]
steps = 1
m = len(grid)
n = len(grid[0])
mark = [[False]*n for _ in range(m)]
mark[0][0] = True
while q:
temp = q
q = []
for i, j in temp:
if i == m-1 and j == n-1:
return steps
# 检查8个方向的相邻坐标
for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1), (i-1, j-1), (i-1, j+1), (i+1, j-1), (i+1, j+1)]:
if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and not mark[x][y]:
q.append([x, y])
mark[x][y] = True
steps += 1
return -1
在题解中，起点grid[0][0]如果为1表示该位置是不可通行的，因为在二进制矩阵中，1代表障碍物，0代表可通行的路径。如果起点即为障碍物，则无法从起点开始任何行动，因此直接返回-1表示在当前的起点位置，找不到任何通往终点的路径。
宽度优先搜索（BFS）是一种从起点开始探索所有可能路径的层级搜索方法，它通过逐层访问所有节点确保在找到目标节点时走过的路径是最短的。BFS首先探索与起点相邻的所有节点，然后再探索这些节点相邻的所有节点，依此类推。这种按层级扩展的特性使得BFS能够保证一旦到达终点时，走过的路径长度是最短的可能路径。
在二进制矩阵的最短路径问题中，允许沿对角线移动可以提供更短的路径选项，这相当于在正常的上下左右移动（4个方向）之外，增加了四个对角线方向的移动。这样的设计使得路径可以更直接地向目标点前进，可能避免了更多的障碍物，从而在许多情况下减少了总的移动步数，更快地到达目标位置。
题解中的描述应该更加明确：只有当单元格的值为0（表示无障碍且可通行）并且该单元格未被标记为已访问时，才会将其加入到队列中进行进一步的探索。这种检查方式是为了确保不会浪费资源去探索已经访问过或者无法通行的单元格。标记和值检查的顺序在实现中是紧密结合的，以避免重复访问和保证只访问开放路径。