Shortest Distance from All Buildings

hard bfs matrix

Problem

In an m×n grid (0 empty, 1 building, 2 obstacle), find an empty cell that minimizes total Manhattan-like grid distance to every building (must be reachable from each).

Inputgrid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

Output7

Center cell (1,2) reaches every building with summed distance 7.

grid (rows ';' cells ',', 0/1/2)

from collections import deque
def shortest_distance(grid):
    m, n = len(grid), len(grid[0])
    dist = [[0]*n for _ in range(m)]
    reach = [[0]*n for _ in range(m)]
    buildings = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 1:
                buildings += 1
                seen = [[False]*n for _ in range(m)]
                q = deque([(r, c, 0)])
                seen[r][c] = True
                while q:
                    x, y, d = q.popleft()
                    for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < m and 0 <= ny < n and not seen[nx][ny] and grid[nx][ny] == 0:
                            seen[nx][ny] = True
                            dist[nx][ny] += d + 1
                            reach[nx][ny] += 1
                            q.append((nx, ny, d + 1))
    best = float("inf")
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 0 and reach[r][c] == buildings:
                best = min(best, dist[r][c])
    return -1 if best == float("inf") else best

function shortestDistance(grid) {
  const m = grid.length, n = grid[0].length;
  const dist = Array.from({length: m}, () => new Array(n).fill(0));
  const reach = Array.from({length: m}, () => new Array(n).fill(0));
  let buildings = 0;
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) {
    if (grid[r][c] !== 1) continue;
    buildings++;
    const seen = Array.from({length: m}, () => new Array(n).fill(false));
    const q = [[r, c, 0]]; seen[r][c] = true;
    while (q.length) {
      const [x, y, d] = q.shift();
      for (const [dx, dy] of [[-1,0],[1,0],[0,-1],[0,1]]) {
        const nx = x + dx, ny = y + dy;
        if (nx < 0 || nx >= m || ny < 0 || ny >= n || seen[nx][ny] || grid[nx][ny] !== 0) continue;
        seen[nx][ny] = true; dist[nx][ny] += d + 1; reach[nx][ny]++;
        q.push([nx, ny, d + 1]);
      }
    }
  }
  let best = Infinity;
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) {
    if (grid[r][c] === 0 && reach[r][c] === buildings) best = Math.min(best, dist[r][c]);
  }
  return best === Infinity ? -1 : best;
}

class Solution {
    public int shortestDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n], reach = new int[m][n];
        int buildings = 0;
        int[][] D = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
            if (grid[r][c] != 1) continue;
            buildings++;
            boolean[][] seen = new boolean[m][n];
            Deque q = new ArrayDeque<>();
            q.add(new int[]{r, c, 0}); seen[r][c] = true;
            while (!q.isEmpty()) {
                int[] p = q.poll();
                for (int[] d : D) {
                    int nx = p[0] + d[0], ny = p[1] + d[1];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || seen[nx][ny] || grid[nx][ny] != 0) continue;
                    seen[nx][ny] = true; dist[nx][ny] += p[2] + 1; reach[nx][ny]++;
                    q.add(new int[]{nx, ny, p[2] + 1});
                }
            }
        }
        int best = Integer.MAX_VALUE;
        for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
            if (grid[r][c] == 0 && reach[r][c] == buildings) best = Math.min(best, dist[r][c]);
        }
        return best == Integer.MAX_VALUE ? -1 : best;
    }
}

int shortestDistance(vector>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector> dist(m, vector(n, 0)), reach = dist;
    int buildings = 0;
    int D[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
        if (grid[r][c] != 1) continue;
        buildings++;
        vector> seen(m, vector(n, false));
        queue> q; q.push({r, c, 0}); seen[r][c] = true;
        while (!q.empty()) {
            auto [x, y, d] = q.front(); q.pop();
            for (auto& dd : D) {
                int nx = x + dd[0], ny = y + dd[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || seen[nx][ny] || grid[nx][ny] != 0) continue;
                seen[nx][ny] = true; dist[nx][ny] += d + 1; reach[nx][ny]++;
                q.push({nx, ny, d + 1});
            }
        }
    }
    int best = INT_MAX;
    for (int r = 0; r < m; r++) for (int c = 0; c < n; c++)
        if (grid[r][c] == 0 && reach[r][c] == buildings) best = min(best, dist[r][c]);
    return best == INT_MAX ? -1 : best;
}

Explanation

We need an empty cell that is close to every building. Instead of testing each empty cell against all buildings, we flip it around: run a BFS from each building and let every reachable empty cell accumulate its distance to that building.

We keep two grids: dist[r][c] sums the distances from each building to that cell, and reach[r][c] counts how many buildings could reach it. For every building we BFS outward over empty cells (0), and for each cell we touch we do dist += d and reach += 1.

After all buildings are processed, a cell is a valid candidate only if reach[r][c] == buildings — meaning every building reached it. Among those valid cells we take the smallest dist as the answer.

Example: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]. The center cell (1,2) can reach all three buildings, and its summed distance is the minimum at 7. The obstacle 2 blocks BFS, so cells walled off from a building never reach the full count.

Using reach elegantly handles obstacles and disconnected pockets: if a cell can't see every building it's simply disqualified, and if no cell qualifies we return -1.

Time: O(b · mn) Space: O(mn)