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

Categories:

题目描述
思路分析
1. 解法一：BFS 最短路（推荐）
相似题目

题目描述

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

思路分析

解法一：BFS 最短路（推荐）

核心思路：

在 8 个方向上进行 BFS，首次到达终点的层数即最短路径长度。

访问过的格子立刻标记，避免重复入队。

若起点或终点为阻塞格，直接返回 -1。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示矩阵边长。

空间复杂度：O(n^2)，用于队列与访问标记。

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
            return -1;
        }

        int[][] dirs = {
                {-1, -1}, {-1, 0}, {-1, 1},
                {0, -1}, {0, 1},
                {1, -1}, {1, 0}, {1, 1}
        };

        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {0, 0});
        grid[0][0] = 1;

        int steps = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int x = cur[0];
                int y = cur[1];

                if (x == n - 1 && y == n - 1) {
                    return steps;
                }

                for (int[] d : dirs) {
                    int nx = x + d[0];
                    int ny = y + d[1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
                        continue;
                    }
                    if (grid[nx][ny] == 1) {
                        continue;
                    }
                    grid[nx][ny] = 1;
                    queue.offer(new int[] {nx, ny});
                }
            }
            steps++;
        }

        return -1;
    }
}

func shortestPathBinaryMatrix(grid [][]int) int {
	n := len(grid)
	if grid[0][0] == 1 || grid[n-1][n-1] == 1 {
		return -1
	}

	dirs := [][]int{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{0, 0})
	grid[0][0] = 1

	steps := 1
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			cur := queue[0]
			queue = queue[1:]
			x, y := cur[0], cur[1]

			if x == n-1 && y == n-1 {
				return steps
			}

			for _, d := range dirs {
				nx := x + d[0]
				ny := y + d[1]
				if nx < 0 || nx >= n || ny < 0 || ny >= n {
					continue
				}
				if grid[nx][ny] == 1 {
					continue
				}
				grid[nx][ny] = 1
				queue = append(queue, [2]int{nx, ny})
			}
		}
		steps++
	}

	return -1
}

相似题目

题目	难度	考察点
542. 01 矩阵	中等	BFS
934. 最短的桥	中等	BFS
773. 滑动谜题	困难	BFS
994. 腐烂的橘子	中等	BFS
847. 访问所有节点的最短路径	困难	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/82084472