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 ```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.