Given an m x n integer grid grid, where each cell contains one of three values:

• $0$ represents empty land that can be freely traversed,

• $1$ represents a building that cannot be passed through,

• $2$ represents an obstacle that cannot be passed through.

You want to place a house on an empty land cell ($0$) such that the sum of shortest distances from the house to all buildings is minimized. Movement is restricted to four directions: up, down, left, and right.

Return the minimum total travel distance for such a placement. If no valid empty land cell can reach all buildings, return $-1$.

Note: The total travel distance is the sum of the shortest path distances from the chosen empty land cell to every building in the grid.

Constraints:

• m == grid.length

• n == grid[i].length

• $1 \leq$ m, n $\leq 50$

• grid[i][j] is either $0$, $1$, or $2$

• There will be at least $1$ building in grid

The key insight is that instead of doing BFS from every empty cell to find distances to all buildings (which would be expensive), we reverse the direction and perform BFS from every building outward across the empty land. For each building, a standard BFS propagates shortest distances to all reachable empty cells. We maintain two auxiliary grids: distSum, which accumulates the total BFS distance contributed to each empty cell from every building, and reachCount, which tracks how many buildings can actually reach each empty cell. After all BFS passes are complete, the answer is the minimum value in distSum among only those empty cells whose reachCount equals the total number of buildings, ensuring the chosen cell is reachable from every building. If no such cell exists, we return $-1$.

Now, let’s look at the solution steps below:

shortestDistance(grid) function:

1. Record the grid dimensions as numRows and numCols. Create two $m \times n$ ...