Walls and gates

Array Breadth-First Search Matrix

63.9% acceptance

Mar 31, 2026

3326

You are given an m x n grid rooms initialized with these three possible values. -1 A wall or an obstacle. 0 A gate. INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

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