二进制矩阵中的最短畅通路径长度

问题描述

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

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

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

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

解题思路

本题需要求最短路径，很自然地想到使用广度优先搜索（BFS）来解决。

我们可以将每个单元格看做一个节点，如果两个单元格相邻且都是 0，则这两个单元格之间有一条无向边，边权为 1。因此，我们可以将整个二维矩阵看做一个无向图，问题就转化为了求从起点到终点的最短路径。

我们可以从起点开始进行 BFS，每次尝试向上、下、左、右、左上、右上、左下、右下 8 个方向扩展。如果扩展出的节点是 0 且没有被访问过，就将这个节点加入队列中，并将其标记为已访问。当我们找到终点时，就可以返回最短路径的长度。

需要注意的是，如果起点或终点为 1，则无法到达终点，返回 -1。

代码示例 (Python)pythonfrom collections import deque

def shortestPathBinaryMatrix(grid): n = len(grid) if grid[0][0] == 1 or grid[n - 1][n - 1] == 1: return -1

directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]    queue = deque([(0, 0, 1)])  # (row, col, distance)    visited = set([(0, 0)])

while queue:        row, col, distance = queue.popleft()        if row == n - 1 and col == n - 1:            return distance

    for dr, dc in directions:            new_row, new_col = row + dr, col + dc            if 0 <= new_row < n and 0 <= new_col < n and grid[new_row][new_col] == 0 and (new_row, new_col) not in visited:                queue.append((new_row, new_col, distance + 1))                visited.add((new_row, new_col))

return -1

复杂度分析

时间复杂度： 由于每个节点最多只会被访问一次，因此时间复杂度为 O(n^2)。* 空间复杂度： 队列中最多会存储 n^2 个节点，因此空间复杂度为 O(n^2)。