Find the Cell with the Smallest Total Walking Distance to All Targets Around Walls

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

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

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

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

Input:  grid = ["xwx"]
Output: -1

The wall separates the two targets, so no cell can reach both.

Minimum Total Walking Distance to All Targets in a Walled Grid

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

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

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.

Hints

1. Walls make walking distance differ from Manhattan distance: in Example 2 the answer is 8, while the same grid without walls gives 4.
2. The chosen cell may itself be a target, and paths may pass through targets; a target's distance to itself is 0.
3. 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.

Approach

Run a breadth-first search from every target over the non-wall cells. Every step costs 1, so the search from a target assigns each cell it reaches that cell's exact walking distance to the target (walking distance is symmetric). For each cell, keep a running total of these distances and a count of how many targets reached it. Invariant: after k targets have been processed, total[cell] is the sum of the cell's distances to those k targets and reach[cell] is the number of them that can reach it. A non-wall cell can reach every target exactly when its count equals the number of targets, so the answer is the smallest total among those cells, or -1 when there are none. Edge cases: a single target gives 0 because the target cell is itself a candidate; walls that split the targets into different regions give -1; empty cells sealed off from the targets are never reached, so they are skipped instead of contributing a false total of 0 or forcing -1; paths may pass through target cells, and a target cell can be the answer. Totals stay below 250,000, so 32-bit integers suffice in every language.

• Time complexity: O(T * R * C), where R x C is the grid size and T <= 100 is the number of targets
• Space complexity: O(R * C)