LeetCode 1091: Shortest Path in Binary Matrix (8-Direction BFS)
LeetCode 1091GraphBFSMatrixToday we solve LeetCode 1091 - Shortest Path in Binary Matrix.
Source: https://leetcode.com/problems/shortest-path-in-binary-matrix/
English
Problem Summary
Given an n x n binary matrix, return the length of the shortest clear path from top-left to bottom-right. You can move in 8 directions, and only cells with value 0 are walkable.
Key Insight
This is an unweighted shortest path problem on a grid graph. BFS guarantees the first time we reach a cell, we used the minimum number of steps. With level-order BFS, the current distance is the path length.
Algorithm
- If start or end is blocked, return -1.
- Push (0,0) into queue and mark visited.
- Expand level by level in 8 directions.
- When reaching (n-1,n-1), return current distance.
- If queue becomes empty, return -1.
Complexity Analysis
Time: O(n^2), each cell is visited at most once.
Space: O(n^2) for queue and visited marks.
Common Pitfalls
- Forgetting diagonal moves (must be 8 directions).
- Not marking visited immediately when enqueueing.
- Off-by-one in path length (start cell counts as 1).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
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}
};
Queue q = new ArrayDeque<>();
q.offer(new int[]{0, 0});
grid[0][0] = 1; // visited
int dist = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
if (r == n - 1 && c == n - 1) return dist;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
if (grid[nr][nc] != 0) continue;
grid[nr][nc] = 1;
q.offer(new int[]{nr, nc});
}
}
dist++;
}
return -1;
}
} func shortestPathBinaryMatrix(grid [][]int) int {
n := len(grid)
if grid[0][0] == 1 || grid[n-1][n-1] == 1 {
return -1
}
dirs := [][2]int{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}
q := [][2]int{{0, 0}}
grid[0][0] = 1
dist := 1
for len(q) > 0 {
size := len(q)
for i := 0; i < size; i++ {
r, c := q[0][0], q[0][1]
q = q[1:]
if r == n-1 && c == n-1 {
return dist
}
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] != 0 {
continue
}
grid[nr][nc] = 1
q = append(q, [2]int{nr, nc})
}
}
dist++
}
return -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;
vector<pair<int,int>> dirs = {
{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}
};
queue<pair<int,int>> q;
q.push({0, 0});
grid[0][0] = 1;
int dist = 1;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
auto [r, c] = q.front(); q.pop();
if (r == n - 1 && c == n - 1) return dist;
for (auto [dr, dc] : dirs) {
int nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
if (grid[nr][nc] != 0) continue;
grid[nr][nc] = 1;
q.push({nr, nc});
}
}
dist++;
}
return -1;
}
};from collections import deque
from typing import List
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
dirs = [
(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1),
]
q = deque([(0, 0)])
grid[0][0] = 1
dist = 1
while q:
for _ in range(len(q)):
r, c = q.popleft()
if r == n - 1 and c == n - 1:
return dist
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
grid[nr][nc] = 1
q.append((nr, nc))
dist += 1
return -1/**
* @param {number[][]} grid
* @return {number}
*/
var shortestPathBinaryMatrix = function(grid) {
const n = grid.length;
if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1;
const dirs = [
[-1, -1], [-1, 0], [-1, 1],
[0, -1], [0, 1],
[1, -1], [1, 0], [1, 1],
];
const q = [[0, 0]];
grid[0][0] = 1;
let dist = 1;
while (q.length) {
const size = q.length;
for (let i = 0; i < size; i++) {
const [r, c] = q.shift();
if (r === n - 1 && c === n - 1) return dist;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] !== 0) continue;
grid[nr][nc] = 1;
q.push([nr, nc]);
}
}
dist++;
}
return -1;
};中文
题目概述
给定一个 n x n 的二进制矩阵，从左上角走到右下角，求最短通路长度。只能走值为 0 的格子，且可以朝 8 个方向移动（含对角线）。
核心思路
这是无权图最短路问题，最适合 BFS。按层扩展时，层数就是当前路径长度。第一次到达终点时，一定是最短路径。
算法步骤
- 若起点或终点被阻塞，直接返回 -1。
- 将 (0,0) 入队并标记已访问。
- 每层按 8 个方向扩展可达格子。
- 一旦到达 (n-1,n-1)，返回当前层数。
- 队列耗尽仍未到达，返回 -1。
复杂度分析
时间复杂度：O(n^2)，每个格子最多访问一次。
空间复杂度：O(n^2)，用于队列与访问标记。
常见陷阱
- 漏掉对角线方向，导致答案偏大或错误。
- 入队后不立即标记访问，造成重复入队。
- 路径长度计数从 0 开始，忽略起点应计为 1。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
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}
};
Queue q = new ArrayDeque<>();
q.offer(new int[]{0, 0});
grid[0][0] = 1;
int dist = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
if (r == n - 1 && c == n - 1) return dist;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
if (grid[nr][nc] != 0) continue;
grid[nr][nc] = 1;
q.offer(new int[]{nr, nc});
}
}
dist++;
}
return -1;
}
} func shortestPathBinaryMatrix(grid [][]int) int {
n := len(grid)
if grid[0][0] == 1 || grid[n-1][n-1] == 1 {
return -1
}
dirs := [][2]int{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}
q := [][2]int{{0, 0}}
grid[0][0] = 1
dist := 1
for len(q) > 0 {
size := len(q)
for i := 0; i < size; i++ {
r, c := q[0][0], q[0][1]
q = q[1:]
if r == n-1 && c == n-1 {
return dist
}
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] != 0 {
continue
}
grid[nr][nc] = 1
q = append(q, [2]int{nr, nc})
}
}
dist++
}
return -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;
vector<pair<int,int>> dirs = {
{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}
};
queue<pair<int,int>> q;
q.push({0, 0});
grid[0][0] = 1;
int dist = 1;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
auto [r, c] = q.front(); q.pop();
if (r == n - 1 && c == n - 1) return dist;
for (auto [dr, dc] : dirs) {
int nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
if (grid[nr][nc] != 0) continue;
grid[nr][nc] = 1;
q.push({nr, nc});
}
}
dist++;
}
return -1;
}
};from collections import deque
from typing import List
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
dirs = [
(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1),
]
q = deque([(0, 0)])
grid[0][0] = 1
dist = 1
while q:
for _ in range(len(q)):
r, c = q.popleft()
if r == n - 1 and c == n - 1:
return dist
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
grid[nr][nc] = 1
q.append((nr, nc))
dist += 1
return -1/**
* @param {number[][]} grid
* @return {number}
*/
var shortestPathBinaryMatrix = function(grid) {
const n = grid.length;
if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1;
const dirs = [
[-1, -1], [-1, 0], [-1, 1],
[0, -1], [0, 1],
[1, -1], [1, 0], [1, 1],
];
const q = [[0, 0]];
grid[0][0] = 1;
let dist = 1;
while (q.length) {
const size = q.length;
for (let i = 0; i < size; i++) {
const [r, c] = q.shift();
if (r === n - 1 && c === n - 1) return dist;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] !== 0) continue;
grid[nr][nc] = 1;
q.push([nr, nc]);
}
}
dist++;
}
return -1;
};
Comments