Medium

题目描述

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

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

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

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

示例 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.length
  • n == grid[i].length
  • 1 <= n <= 100
  • grid[i][j] 为 0 或 1

解题思路

这是一个典型的求最短路径问题，使用 广度优先搜索（BFS） 是最适合的解法。

核心思路：

  1. 如果起点或终点为 1，直接返回 -1
  2. 从起点 (0,0) 开始 BFS，每次向 8 个方向扩展
  3. 使用队列记录当前位置和路径长度
  4. 使用访问标记避免重复访问
  5. 第一次到达终点时的路径长度就是最短路径

算法步骤：

  • 初始化队列，将起点和路径长度 1 入队
  • 定义 8 个方向的偏移量：上下左右及四个对角线方向
  • BFS 遍历：
    • 取出队头元素，检查是否到达终点
    • 向 8 个方向扩展，检查边界和障碍物
    • 将有效的下一步位置入队，路径长度 +1
  • 如果队列为空仍未到达终点，返回 -1

优化点：

  • 可以直接在原矩阵上标记访问过的位置为 1，节省空间
  • 提前检查特殊情况（起点终点为 1）

代码实现

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
        if (n == 1) return 1;
        
        queue<pair<pair<int, int>, int>> q;
        q.push({{0, 0}, 1});
        grid[0][0] = 1;
        
        int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
        int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
        
        while (!q.empty()) {
            auto curr = q.front();
            q.pop();
            int x = curr.first.first;
            int y = curr.first.second;
            int dist = curr.second;
            
            for (int i = 0; i < 8; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                    if (nx == n-1 && ny == n-1) return dist + 1;
                    grid[nx][ny] = 1;
                    q.push({{nx, ny}, dist + 1});
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] == 1 or grid[n-1][n-1] == 1:
            return -1
        if n == 1:
            return 1
        
        queue = deque([(0, 0, 1)])
        grid[0][0] = 1
        
        directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
        
        while queue:
            x, y, dist = queue.popleft()
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
                    if nx == n-1 and ny == n-1:
                        return dist + 1
                    grid[nx][ny] = 1
                    queue.append((nx, ny, dist + 1))
        
        return -1

public class Solution {
    public int ShortestPathBinaryMatrix(int[][] grid) {
        int n = grid.Length;
        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
        if (n == 1) return 1;
        
        Queue<(int x, int y, int dist)> queue = new Queue<(int, int, int)>();
        queue.Enqueue((0, 0, 1));
        grid[0][0] = 1;
        
        int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
        
        while (queue.Count > 0) {
            var (x, y, dist) = queue.Dequeue();
            
            for (int i = 0; i < 8; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                    if (nx == n-1 && ny == n-1) return dist + 1;
                    grid[nx][ny] = 1;
                    queue.Enqueue((nx, ny, dist + 1));
                }
            }
        }
        
        return -1;
    }
}

var shortestPathBinaryMatrix = function(grid) {
    const n = grid.length;
    if (grid[0][0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)最坏情况下需要访问矩阵中的每个单元格
空间复杂度O(n²)队列中最多存储 O(n²) 个节点，原地修改节约了访问数组的空间

相关题目