Empty Grid Cell With the Smallest Total Walking Distance to All Buildings
Company: Google
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a map as a grid of `m` rows and `n` columns. Each cell holds one of three values:
- `0`: empty land, which you may walk through and where a new site may be placed;
- `1`: a building, which you cannot walk through;
- `2`: an obstacle, which you cannot walk through.
From a cell you may move one step up, down, left or right. Choose an empty cell that minimizes the sum, over all buildings, of the shortest walking distance from that cell to the building, and return that minimum sum. If no empty cell can reach every building, return `-1`.
### Function Signature
```python
def min_total_distance_to_buildings(grid: list[list[int]]) -> int:
```
### Rules
- The distance from an empty cell to a building is the smallest number of steps in a path that starts at the empty cell, moves only through empty cells, and whose final step enters the building's cell. If no such path exists, that building is unreachable from the cell.
- Buildings and obstacles are never walked through, and they can never be the chosen cell. A building can appear in a path only as its final cell.
- An empty cell is a valid choice only if every building in the grid is reachable from it.
- Return the smallest total distance over all valid cells. The answer is a single integer, so it does not matter which cell achieves it when several tie.
- Return `-1` when there is no valid cell, including when the grid contains no building at all or no empty cell.
### Constraints
- `1 <= m, n <= 50`
- Every row has exactly `n` entries, and each entry is `0`, `1` or `2`.
- Any total distance is below `2500 * 2500 = 6,250,000`, well within a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: grid = [[1, 0, 1], [0, 0, 0], [2, 1, 0]]
Output: 4
```
```text
1 0 1
0 0 0
2 1 0
```
The buildings are at (0, 0), (0, 2) and (2, 1), and (2, 0) is an obstacle. Cell (0, 1) is 1 step from (0, 0), 1 step from (0, 2), and 2 steps from (2, 1) through (1, 1), for a total of 4. The other empty cells total 5 for (1, 1), 6 for (1, 0), 6 for (1, 2) and 7 for (2, 2).
**Example 2**
```text
Input: grid = [[1, 1, 0]]
Output: -1
```
The only empty cell is (0, 2). Building (0, 1) is one step away, but reaching building (0, 0) would require walking through (0, 1), which is a building. No empty cell reaches every building.
**Example 3**
```text
Input: grid = [[0, 2], [2, 0]]
Output: -1
```
The grid contains no building, so by the rules the answer is `-1`.
Overview: Given a grid of empty land, buildings and obstacles, find the empty cell with the smallest total walking distance to every building using four-directional moves, or return -1 when no cell reaches them all. It tests breadth-first search on grids, reachability filtering and edge cases.
You are given a map as a grid `grid` of `m` rows and `n` columns. Each cell holds one of three values:
- `0`: empty land, which you may walk through and where a new site may be placed;
- `1`: a building, which you cannot walk through;
- `2`: an obstacle, which you cannot walk through.
From a cell you may move one step up, down, left or right. Choose an empty cell that minimizes the sum, over all buildings, of the shortest walking distance from that cell to the building, and return that minimum sum. If no empty cell can reach every building, return `-1`.
Implement `min_total_distance_to_buildings(grid)`. Cells are written as (row, column), counted from 0.
**Rules**
- The distance from an empty cell to a building is the smallest number of steps in a path that starts at the empty cell, moves only through empty cells, and whose final step enters the building's cell. If no such path exists, that building is unreachable from the cell.
- Buildings and obstacles are never walked through, and they can never be the chosen cell. A building can appear in a path only as its final cell.
- An empty cell is a valid choice only if every building in the grid is reachable from it.
- Return the smallest total distance over all valid cells. The answer is a single integer, so it does not matter which cell achieves it when several tie.
- Return `-1` when there is no valid cell, including when the grid contains no building at all or no empty cell.
**Example 1**
```
Input: grid = [[1, 0, 1], [0, 0, 0], [2, 1, 0]]
Output: 4
```
The buildings are at (0, 0), (0, 2) and (2, 1), and (2, 0) is an obstacle. Cell (0, 1) is 1 step from (0, 0), 1 step from (0, 2), and 2 steps from (2, 1) through (1, 1), for a total of 4. The other empty cells total 5 for (1, 1), 6 for (1, 0), 6 for (1, 2) and 7 for (2, 2).
**Example 2**
```
Input: grid = [[1, 1, 0]]
Output: -1
```
The only empty cell is (0, 2). Building (0, 1) is one step away, but reaching building (0, 0) would require walking through (0, 1), which is a building. No empty cell reaches every building.
**Constraints**
- `1 <= m, n <= 50`
- Every row has exactly `n` entries, and each entry is `0`, `1` or `2`.
- Any total distance is below `2500 * 2500 = 6,250,000`, well within a 32-bit signed integer: the answer never exceeds 2^31 - 1, so Java and C++ return `int`.
Constraints
- 1 <= m, n <= 50
- Every row has exactly n entries, and each entry is 0, 1 or 2.
- Any total distance is below 2500 * 2500 = 6,250,000, well within a 32-bit signed integer.
Examples
Input: ([[1, 0, 1], [0, 0, 0], [2, 1, 0]],)
Expected Output: 4
Explanation: Source Example 1: cell (0, 1) totals 1 + 1 + 2 = 4; the other empty cells total 5, 6, 6 and 7.
Input: ([[1, 1, 0]],)
Expected Output: -1
Explanation: Source Example 2: the only empty cell would have to walk through building (0, 1) to reach building (0, 0), so no cell is valid.
Hints
- A cell is a valid site only if every building can be reached from it; a cell that is very close to some buildings but cut off from even one of them cannot be chosen.
- Movement stops at buildings and obstacles: a path may end on a building but never pass through one, so a walking distance can be longer than the straight grid distance.
- When there is no building, no empty cell, or no empty cell that reaches every building, the answer is -1.