Minimize Total Grid Distance to Every Building

Problem Statement

You are given an m x n grid of integers representing a map where each cell contains one of three values:

• 0: Empty land where a vehicle dispatch hub can be placed.
• 1: A building that needs service.
• 2: An obstacle that vehicles cannot pass through.

You want to place a single dispatch hub on an empty land cell (0) such that the sum of shortest travel distances from the hub to every building (1) is minimized.

A vehicle can only move up, down, left, or right to an adjacent empty land cell (0). Vehicles cannot traverse through obstacles (2) or other buildings (1). The distance between two adjacent cells is 1.

Return the minimum total distance to all buildings. If it is impossible to reach all buildings from any empty land cell, return -1.

Function Interface

def shortest_distance(grid: list[list[int]]) -> int:
    pass

Examples

Example 1

Input:
grid = [
    [1, 0, 2, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0]
]
Output: 7
Explanation:
Placing the hub at grid[1][2] allows shortest paths to the three buildings of lengths 3, 3, and 1, respectively. Total distance = 3 + 3 + 1 = 7, which is optimal.

Example 2

Input:
grid = [
    [1, 2, 0],
    [2, 2, 0],
    [0, 0, 1]
]
Output: -1
Explanation:
The building at (0, 0) is surrounded by obstacles and cannot be reached by any empty land cell.

Constraints

• m == len(grid)
• n == len(grid[i])
• 1 <= m, n <= 100
• grid[i][j] is either 0, 1, or 2.
• There is at least one building (1) on the grid.