# LeetCode 317: Shortest Distance from All Buildings

## Problem Restatement

We are given an `m x n` grid.

Each cell has one of three values:

| Value | Meaning |
|---:|---|
| `0` | Empty land |
| `1` | Building |
| `2` | Obstacle |

We want to build a house on an empty land cell.

The house must be able to reach every building by moving only up, down, left, and right. Buildings and obstacles cannot be passed through.

Return the minimum total travel distance from one empty land cell to all buildings. If no empty land cell can reach all buildings, return `-1`. The problem statement defines `0` as passable empty land, `1` as a building, and `2` as an obstacle.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A grid of `0`, `1`, and `2` |
| Output | Minimum total distance from one empty land cell to all buildings |
| Movement | Up, down, left, right |
| Build location | Must be a `0` cell |
| Blocked cells | Cannot pass through `1` or `2` |

Function shape:

```python
def shortestDistance(grid: list[list[int]]) -> int:
    ...
```

## Examples

Example:

```python
grid = [
    [1, 0, 2, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0],
]
```

There are three buildings:

```text
(0, 0), (0, 4), (2, 2)
```

The best empty land cell is:

```text
(1, 2)
```

Distances:

| Building | Distance to `(1, 2)` |
|---|---:|
| `(0, 0)` | `3` |
| `(0, 4)` | `3` |
| `(2, 2)` | `1` |

Total:

```python
3 + 3 + 1 = 7
```

Output:

```python
7
```

## First Thought: BFS From Every Empty Land

One direct method is:

1. For every empty land cell.
2. Run BFS from that cell.
3. Find the distance to every building.
4. Sum the distances.
5. Keep the minimum valid sum.

This is correct, but it may repeat too much work.

If there are many empty cells, we run many BFS searches.

In the worst case, this costs roughly:

```python
O(E * m * n)
```

where `E` is the number of empty cells.

We can do better by reversing the direction.

## Key Insight

Instead of BFS from every empty land cell, run BFS from every building.

For each building, BFS computes the shortest distance from that building to every reachable empty land cell.

We maintain two matrices:

| Matrix | Meaning |
|---|---|
| `dist[r][c]` | Total distance from all processed buildings to this empty cell |
| `reach[r][c]` | Number of buildings that can reach this empty cell |

After BFS from every building, an empty cell is valid only if:

```python
reach[r][c] == total_buildings
```

Among those valid cells, choose the smallest `dist[r][c]`.

This works because shortest path distance in an unweighted grid is exactly what BFS computes.

## BFS From One Building

For one building at `(start_r, start_c)`:

1. Start BFS from the building.
2. Move only through empty land cells.
3. Track distance by BFS layers.
4. For every reached empty cell:
   - Add the distance to `dist[r][c]`.
   - Increment `reach[r][c]`.

We do not move through buildings or obstacles.

## Algorithm

1. Count all buildings.
2. Create `dist` and `reach` matrices filled with zero.
3. For each building:
   - Run BFS.
   - Update `dist` and `reach` for all reachable empty cells.
4. Scan every cell:
   - It must be empty land.
   - It must be reachable from every building.
   - Use its total distance as a candidate answer.
5. Return the minimum candidate.
6. If no candidate exists, return `-1`.

## Correctness

BFS from a building visits empty cells in increasing distance order. Since every move has cost `1`, the first time BFS reaches an empty cell, that distance is the shortest distance from the building to that cell.

The algorithm runs this BFS once for every building. Therefore, for each empty cell, `dist[r][c]` accumulates the shortest distances from all buildings that can reach it, and `reach[r][c]` counts how many buildings can reach it.

An empty cell is a valid house location exactly when every building can reach it. This is equivalent to:

```python
reach[r][c] == total_buildings
```

For each valid empty cell, `dist[r][c]` is the total travel distance from that cell to all buildings. The algorithm returns the minimum such value.

Therefore, the returned answer is exactly the shortest possible total travel distance. If no empty cell is reachable from all buildings, no valid candidate is found and the algorithm correctly returns `-1`.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `m` | Number of rows |
| `n` | Number of columns |
| `B` | Number of buildings |

| Metric | Value | Why |
|---|---:|---|
| Time | `O(Bmn)` | Each building runs one BFS over the grid |
| Space | `O(mn)` | `dist`, `reach`, `visited`, and queue |

## Implementation

```python
from collections import deque

class Solution:
    def shortestDistance(self, grid: list[list[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        dist = [[0] * n for _ in range(m)]
        reach = [[0] * n for _ in range(m)]

        buildings = []

        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    buildings.append((r, c))

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1),
        ]

        def bfs(start_r: int, start_c: int) -> None:
            queue = deque([(start_r, start_c, 0)])
            visited = [[False] * n for _ in range(m)]
            visited[start_r][start_c] = True

            while queue:
                r, c, d = queue.popleft()

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if not (0 <= nr < m and 0 <= nc < n):
                        continue

                    if visited[nr][nc]:
                        continue

                    if grid[nr][nc] != 0:
                        continue

                    visited[nr][nc] = True
                    dist[nr][nc] += d + 1
                    reach[nr][nc] += 1

                    queue.append((nr, nc, d + 1))

        for r, c in buildings:
            bfs(r, c)

        total_buildings = len(buildings)
        answer = float("inf")

        for r in range(m):
            for c in range(n):
                if grid[r][c] != 0:
                    continue

                if reach[r][c] != total_buildings:
                    continue

                answer = min(answer, dist[r][c])

        if answer == float("inf"):
            return -1

        return answer
```

## Code Explanation

We store the grid dimensions:

```python
m = len(grid)
n = len(grid[0])
```

`dist` accumulates total distances.

```python
dist = [[0] * n for _ in range(m)]
```

`reach` counts how many buildings can reach each empty cell.

```python
reach = [[0] * n for _ in range(m)]
```

Then we collect all buildings.

```python
buildings = []

for r in range(m):
    for c in range(n):
        if grid[r][c] == 1:
            buildings.append((r, c))
```

The BFS starts from one building.

```python
queue = deque([(start_r, start_c, 0)])
```

Each queue entry stores row, column, and distance from the building.

Each BFS needs its own `visited` matrix.

```python
visited = [[False] * n for _ in range(m)]
```

When BFS sees a neighbor, it first checks boundaries.

```python
if not (0 <= nr < m and 0 <= nc < n):
    continue
```

Then it rejects already visited cells.

```python
if visited[nr][nc]:
    continue
```

Then it rejects buildings and obstacles.

```python
if grid[nr][nc] != 0:
    continue
```

Only empty land cells can be visited.

For a valid empty cell, update the distance and reach count.

```python
dist[nr][nc] += d + 1
reach[nr][nc] += 1
```

After running BFS from every building, scan all empty cells.

```python
if reach[r][c] != total_buildings:
    continue
```

This keeps only cells reachable from every building.

Then choose the smallest total distance.

```python
answer = min(answer, dist[r][c])
```

If no valid empty land was found, return `-1`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.shortestDistance([
        [1, 0, 2, 0, 1],
        [0, 0, 0, 0, 0],
        [0, 0, 1, 0, 0],
    ]) == 7

    assert s.shortestDistance([
        [1, 0],
    ]) == 1

    assert s.shortestDistance([
        [1],
    ]) == -1

    assert s.shortestDistance([
        [1, 2, 0],
    ]) == -1

    assert s.shortestDistance([
        [1, 0, 1],
    ]) == 2

    assert s.shortestDistance([
        [1, 0, 0],
        [2, 2, 0],
        [1, 0, 0],
    ]) == 6

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Multiple buildings and obstacle |
| `[1, 0]` | One building, one empty land |
| `[[1]]` | No place to build |
| Building blocked by obstacle | No reachable empty land from all buildings |
| Two buildings with one middle land | Simple minimum |
| Maze-like grid | Checks path distance around blockers |