Shortest distance from all buildings

Array Breadth-First Search Matrix

44.9% acceptance

Mar 31, 2026

1988

343

You are given an m x n grid grid of values 0, 1, or 2, where: each 0 marks an empty land that you can pass by freely, each 1 marks a building that you cannot pass through, and each 2 marks an obstacle that you cannot pass through. You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right. Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1. The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn shortest_distance(grid: Vec<Vec<i32>>) -> i32 {
    use std::collections::VecDeque;
    let m = grid.len();
    let n = grid[0].len();
    let mut total_dist = vec![vec![0i32; n]; m];
    let mut reach_count = vec![vec![0i32; n]; m];
    let mut buildings = 0;
    let dirs = [(0i32,1i32),(0,-1),(1,0),(-1,0)];

    for i in 0..m {
      for j in 0..n {
        if grid[i][j] == 1 {
          buildings += 1;
          let mut visited = vec![vec![false; n]; m];
          let mut queue = VecDeque::new();
          queue.push_back((i, j, 0i32));
          visited[i][j] = true;
          while let Some((r, c, dist)) = queue.pop_front() {
            for &(dr, dc) in &dirs {
              let nr = r as i32 + dr;
              let nc = c as i32 + dc;
              if nr >= 0 && nr < m as i32 && nc >= 0 && nc < n as i32 {
                let nr = nr as usize;
                let nc = nc as usize;
                if !visited[nr][nc] && grid[nr][nc] == 0 {
                  visited[nr][nc] = true;
                  total_dist[nr][nc] += dist + 1;
                  reach_count[nr][nc] += 1;
                  queue.push_back((nr, nc, dist + 1));
                }
              }
            }
          }
        }
      }
    }

    let mut ans = i32::MAX;
    for i in 0..m {
      for j in 0..n {
        if grid[i][j] == 0 && reach_count[i][j] == buildings {
          ans = ans.min(total_dist[i][j]);
        }
      }
    }
    if ans == i32::MAX { -1 } else { ans }
  }
}