Leetcode 1091：二进制矩阵中的最短路径（超详细的解法！！！）_矩阵中的最短路径(从左上角到右下角)

在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。

一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, ..., C_k 组成：

• 相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角）
• C_1 位于 (0, 0)（即，值为 grid[0][0]）
• C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）
• 如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）

返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。

示例 1：

输入：[[0,1],[1,0]]
输出：2
1
2

示例 2：

输入：[[0,0,0],[1,1,0],[1,1,0]]
输出：4 
1
2

提示：

1. 1 <= grid.length == grid[0].length <= 100
2. grid[i][j] 为 0 或 1

解题思路

很明显对于最短路径问题，我们可以使用bfs来解。因为是求解最长路径长度，所以我们可以在队列中直接添加路径长度即可。

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if not grid:
            return -1
        r, c = len(grid), len(grid[0])
        if grid[0][0] == 1 or grid[-1][-1] == 1:
            return -1
        
        dire = [[1, 0], [-1, 0], [0, -1], [0, 1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
        q = [(0, 0, 1)]
        while len(q):
            m, n, l = q.pop(0)
            if m == r-1 and n == c-1:
                return l
            for i, j in dire:
                nx, ny = m + i, n + j
                if nx >= 0 and nx < r and ny >= 0 and ny < c and not grid[nx][ny]:
                    q.append((nx, ny, l + 1))
                    grid[nx][ny] = 1

        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！