Find the Cell with the Smallest Total Walking Distance to All Targets Around Walls
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a 2D grid in which every cell is a target `'x'`, an empty cell `'.'` or a wall `'w'`. Find a cell whose total walking distance to all targets is as small as possible, and return that total.
Walls cannot be crossed. The chosen cell may be an empty cell or a target cell.
### Function Signature
```python
def min_total_distance(grid: list[str]) -> int:
```
### Rules
- A step moves to an adjacent cell up, down, left or right, and costs 1. Paths may pass through empty cells and target cells, but never through walls.
- The walking distance between two cells is the length of the shortest such path. A target's distance to itself is `0`.
- A candidate cell is any non-wall cell. Its total is the sum of its walking distances to every target.
- Return the minimum total over all candidate cells that can reach every target. If no cell can reach every target, return `-1`.
### Constraints
- `1 <= len(grid) <= 50` and `1 <= len(grid[i]) <= 50`, and all rows have the same length
- Every character is `'x'`, `'.'` or `'w'`.
- The grid contains between 1 and 100 targets.
### Examples
**Example 1**
```text
Input: grid = [
"x.x",
"...",
".x."
]
Output: 4
```
The cell `(0, 1)` is at distance 1, 1 and 2 from the three targets. No cell does better.
**Example 2**
```text
Input: grid = [
"x.w.x",
"..w..",
"....."
]
Output: 8
```
The walls force every path between the two targets through `(2, 2)`, so they are 8 steps apart, and no cell can have a total below 8. The cell `(2, 2)` itself is 4 steps from each target. Without the walls the answer would be 4.
**Example 3**
```text
Input: grid = ["xwx"]
Output: -1
```
The wall separates the two targets, so no cell can reach both.
Overview: Given a grid of targets, empty cells and walls, find the cell with the smallest total walking distance to every target, where paths cannot cross walls, or report that no cell reaches them all. Tests breadth-first search from multiple sources, accumulating distances and handling unreachable regions.
You are given a 2D grid `grid` as a list of strings of equal length. Every cell is a target `'x'`, an empty cell `'.'` or a wall `'w'`. Find a cell whose total walking distance to all targets is as small as possible, and return that total.
Walls cannot be crossed. The chosen cell may be an empty cell or a target cell.
### Rules
- A step moves to an adjacent cell up, down, left or right, and costs 1. Paths may pass through empty cells and target cells, but never through walls.
- The walking distance between two cells is the length of the shortest such path. A target's distance to itself is `0`.
- A candidate cell is any non-wall cell. Its total is the sum of its walking distances to every target.
- Return the minimum total over all candidate cells that can reach every target. If no cell can reach every target, return `-1`.
Only the minimum total is returned, so it does not matter which cell attains it when several cells tie. Every total is below 250,000 (at most 100 targets, each fewer than 2,500 steps away), so the result fits in a signed 32-bit integer. Cells are written as `(row, column)`, 0-indexed.
### Examples
**Example 1**
```text
Input: grid = ["x.x", "...", ".x."]
Output: 4
```
The empty cell `(0, 1)` is at distance 1, 1 and 2 from the three targets. No cell does better.
**Example 2**
```text
Input: grid = ["x.w.x", "..w..", "....."]
Output: 8
```
The walls force every path between the two targets through `(2, 2)`, so they are 8 steps apart and no cell can have a total below 8. The cell `(2, 2)` itself is 4 steps from each target. Without the walls the answer would be 4.
### Constraints
- `1 <= len(grid) <= 50` and `1 <= len(grid[i]) <= 50`, and all rows have the same length
- Every character is `'x'`, `'.'` or `'w'`.
- The grid contains between 1 and 100 targets.
Constraints
- 1 <= len(grid) <= 50 and 1 <= len(grid[i]) <= 50, and all rows have the same length
- Every character is 'x', '.' or 'w'.
- The grid contains between 1 and 100 targets.
Examples
Input: (['x.x', '...', '.x.'],)
Expected Output: 4
Explanation: Source example 1: empty cell (0, 1) totals 1 + 1 + 2 = 4; the best target cell totals 5.
Input: (['x.w.x', '..w..', '.....'],)
Expected Output: 8
Explanation: Source example 2: walls force the two targets 8 steps apart, so the answer is 8, not the wall-free 4.
Hints
- Walls make walking distance differ from Manhattan distance: in Example 2 the answer is 8, while the same grid without walls gives 4.
- The chosen cell may itself be a target, and paths may pass through targets; a target's distance to itself is 0.
- A cell counts only if it can reach every target. Empty cells sealed off from the targets are simply not candidates; -1 is returned only when no cell reaches all targets.