Description
Given a 2D grid with empty land (0), buildings (1), and obstacles (2), find an empty land to build a house that has minimum total distance to all buildings.
Examples
Input:
grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]Output:
7Explanation:
Build at (1,2) for minimum total distance.
Input:
grid = [[1]]Output:
1Explanation:
Minimal case with a single-element matrix.
Input:
grid = [[1,0,0],[2,0,0],[1,0,1]]Output:
4Explanation:
Three buildings at positions (0,0), (2,0), and (2,2). The optimal empty land position is (1,1) with distances: to (0,0)=2, to (2,0)=2, to (2,2)=2, total=6. Position (0,2) gives total distance 8, which is worse.
Constraints
- •
m == grid.length - •
n == grid[i].length - •
1 ≤ m, n ≤ 50