Minimize Total Grid Distance to Every Building

Given a rectangular grid containing buildings, empty land, and obstacles, choose an empty cell that minimizes the sum of its shortest-path distances to every building. Return that minimum sum, or -1 if no empty cell can reach every building.

Input

• grid: a two-dimensional integer array. A 0 is empty land, a 1 is a building, and a 2 is an obstacle.

Output

Return the minimum total distance as an integer. Return only the distance, so tied locations do not require a tie-break.

Constraints and Edge Cases

• For this practice version, the grid has between 1 and 50 rows and between 1 and 50 columns.
• At least one building is present.
• One move enters an orthogonally adjacent cell and has cost one. Diagonal movement is not allowed.
• Intermediate cells on a path must be empty land. A building may be the destination, but a path cannot pass through it to reach another building.
• Obstacles cannot be entered.
• If no empty land exists, or no empty cell reaches every building, return -1.

Example 1

grid = [[1,0,2], [0,0,0], [2,0,1]]
output = 4

The center cell has distance two to each building, for a total of four. No candidate has a smaller sum.

Example 2

grid = [[1,0,1,0,1]]
output = -1

The middle building blocks travel between the two empty cells. Neither candidate can reach all three buildings without passing through a building.

Minimize Total Grid Distance to Every Building

Approach

Run a breadth-first search from each building, admitting only empty cells after the starting building. Reversing any path found this way gives a legal path from the empty cell to that building: all intermediate cells remain empty, and the building is the final destination. Never enqueue a different building or an obstacle.

For each reached empty cell, add its BFS distance to an accumulated total and increment the number of buildings that reached it. A visitation stamp prevents counting a cell twice during one BFS while allowing later buildings to visit it independently. After all searches, consider only empty cells whose reach count equals the total building count, and return the smallest accumulated sum. If none qualify, return -1.

Unit-cost BFS visits cells in nondecreasing distance, so the first visit to an empty cell gives its exact shortest-path distance to that search's building. Its accumulated total is therefore the sum of exact distances from every building that can reach it. The reach-count condition is precisely the feasibility requirement, and taking the minimum over these feasible empty cells proves the result. Buildings cannot accidentally connect otherwise separated empty regions because they are never admitted as intermediate nodes.

With B buildings and RC cells, the worst-case time is O(BRC), and the distance, reach, visitation and queue storage is O(RC). The grid is not modified. A loose bound of 2500 buildings times fewer than 2500 steps per reachable path keeps every total within signed 32-bit range.

• Time complexity: O(B * rows * columns), where B is the number of buildings.
• Space complexity: O(rows * columns) auxiliary space.