Shortest path in binary matrix

Array Breadth-First Search Matrix

51.1% acceptance

Feb 25, 2026

7386

274

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1. A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that: All the visited cells of the path are 0. All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner). The length of a clear path is the number of visited cells of this path.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn shortest_path_binary_matrix(mut grid: Vec<Vec<i32>>) -> i32 {
    let n = grid.len();
    if grid[0][0] == 1 || grid[n-1][n-1] == 1 { return -1; }
    if n == 1 { return 1; }
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((0usize, 0usize, 1i32));
    grid[0][0] = 1;
    while let Some((r, c, dist)) = queue.pop_front() {
      for dr in -1i32..=1 {
        for dc in -1i32..=1 {
          if dr == 0 && dc == 0 { continue; }
          let nr = r as i32 + dr;
          let nc = c as i32 + dc;
          if nr < 0 || nr >= n as i32 || nc < 0 || nc >= n as i32 { continue; }
          let (nr, nc) = (nr as usize, nc as usize);
          if grid[nr][nc] != 0 { continue; }
          if nr == n-1 && nc == n-1 { return dist + 1; }
          grid[nr][nc] = 1;
          queue.push_back((nr, nc, dist + 1));
        }
      }
    }
    -1
  }
}