1091. 二进制矩阵中的最短路径

题目描述

输入一个 n x n 的矩阵 grid，每格是 0 或 1。

畅通路径从左上角 (0, 0) 出发，到右下角 (n - 1, n - 1) 结束，途经的每一格都必须是 0。相邻两步之间可以朝 8 个方向之一移动，即两格共用一条边或一个角。

路径长度等于路径经过的格子总数（包含起点和终点）。返回最短畅通路径的长度；如果不存在，返回 -1。

示例 1

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

解释：从 (0,0) 斜着走到 (1,1)，共经过 2 格。

示例 2

输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
输出：4

解释：路径 (0,0) -> (0,1) -> (1,2) -> (2,2)，共 4 格。

示例 3

输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
输出：-1

解释：起点 (0,0) 是 1，无法出发。

数据范围

n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] 是 0 或 1。

解题思路

无权图上的最短路用 BFS。每个 0 格是一个节点，与八个方向上的 0 格相连。起点或终点是 1 时直接返回 -1。从 (0,0) 出发按层扩展，dist 表示当前层格子的路径长度（起点为 1）。入队时就把格子改成 1 作为已访问标记。某一层中出现终点时，返回该层的 dist。

为什么正确

第 dist 层的 frontier 恰好是所有最短路径长度为 dist 的格子，它们都已被标记。

复杂度分析

时间 O(n²)：每个格子最多入队一次，每次检查 8 个方向。空间 O(n²)。

易错点

路径长度按格子数计算，起点自身算 1，所以 dist 从 1 开始。别忘了起点或终点本身被堵住的情况，以及 n=1 时起点就是终点。邻居要检查八个方向，不是四个。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

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

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) {
            return -1;
        }
        grid[0][0] = 1;
        List<int[]> frontier = new ArrayList<>();
        frontier.add(new int[]{0, 0});
        int dist = 1;
        while (!frontier.isEmpty()) {
            List<int[]> nxt = new ArrayList<>();
            for (int[] p : frontier) {
                int x = p[0], y = p[1];
                if (x == n - 1 && y == n - 1) {
                    return dist;
                }
                for (int dx = -1; dx <= 1; dx++) {
                    for (int dy = -1; dy <= 1; dy++) {
                        int nx = x + dx, ny = y + dy;
                        if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                            grid[nx][ny] = 1;
                            nxt.add(new int[]{nx, ny});
                        }
                    }
                }
            }
            frontier = nxt;
            dist++;
        }
        return -1;
    }
}

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if (grid[0][0] || grid[n - 1][n - 1]) {
            return -1;
        }
        grid[0][0] = 1;
        vector<pair<int,int>> frontier = {{0, 0}};
        int dist = 1;
        while (!frontier.empty()) {
            vector<pair<int,int>> nxt;
            for (auto [x, y] : frontier) {
                if (x == n - 1 && y == n - 1) {
                    return dist;
                }
                for (int dx = -1; dx <= 1; dx++) {
                    for (int dy = -1; dy <= 1; dy++) {
                        int nx = x + dx, ny = y + dy;
                        if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                            grid[nx][ny] = 1;
                            nxt.push_back({nx, ny});
                        }
                    }
                }
            }
            frontier = nxt;
            dist++;
        }
        return -1;
    }
};

func shortestPathBinaryMatrix(grid [][]int) int {
	n := len(grid)
	if grid[0][0] != 0 || grid[n-1][n-1] != 0 {
		return -1
	}
	grid[0][0] = 1
	frontier := [][2]int{{0, 0}}
	dist := 1
	for len(frontier) > 0 {
		nxt := [][2]int{}
		for _, p := range frontier {
			x, y := p[0], p[1]
			if x == n-1 && y == n-1 {
				return dist
			}
			for dx := -1; dx <= 1; dx++ {
				for dy := -1; dy <= 1; dy++ {
					nx, ny := x+dx, y+dy
					if nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0 {
						grid[nx][ny] = 1
						nxt = append(nxt, [2]int{nx, ny})
					}
				}
			}
		}
		frontier = nxt
		dist++
	}
	return -1
}

var shortestPathBinaryMatrix = function(grid) {
    const n = grid.length;
    if (grid[0][0] || grid[n - 1][n - 1]) {
        return -1;
    }
    grid[0][0] = 1;
    let frontier = [[0, 0]];
    let dist = 1;
    while (frontier.length > 0) {
        const nxt = [];
        for (const [x, y] of frontier) {
            if (x === n - 1 && y === n - 1) {
                return dist;
            }
            for (let dx = -1; dx <= 1; dx++) {
                for (let dy = -1; dy <= 1; dy++) {
                    const nx = x + dx, ny = y + dy;
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] === 0) {
                        grid[nx][ny] = 1;
                        nxt.push([nx, ny]);
                    }
                }
            }
        }
        frontier = nxt;
        dist++;
    }
    return -1;
};

function shortestPathBinaryMatrix(grid: number[][]): number {
    const n = grid.length;
    if (grid[0][0] || grid[n - 1][n - 1]) {
        return -1;
    }
    grid[0][0] = 1;
    let frontier: number[][] = [[0, 0]];
    let dist = 1;
    while (frontier.length > 0) {
        const nxt: number[][] = [];
        for (const [x, y] of frontier) {
            if (x === n - 1 && y === n - 1) {
                return dist;
            }
            for (let dx = -1; dx <= 1; dx++) {
                for (let dy = -1; dy <= 1; dy++) {
                    const nx = x + dx, ny = y + dy;
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] === 0) {
                        grid[nx][ny] = 1;
                        nxt.push([nx, ny]);
                    }
                }
            }
        }
        frontier = nxt;
        dist++;
    }
    return -1;
}

载入编辑器，自己跑一遍 →

图论专题的其他题目

查看图论全部题目 →