hardMath / GeometryPure DSA~25 min
Minimum Total Travel to a Common Depot
Field teams are positioned on a grid (1s mark a team in a binary grid). Choose a single depot cell to minimize the total Manhattan distance everyone travels to reach it.
Problem
Given an m x n binary grid where each 1 marks a team's home, return the minimum total Manhattan distance to a single meeting point. Distance between (r1,c1) and (r2,c2) is |r1-r2| + |c1-c2|. The meeting point may be any cell.
Input
A 2D binary grid (0/1) with at least one 1.
Output
An integer: the minimum total Manhattan travel distance.
Constraints
- m == grid.length, n == grid[0].length
- 1 <= m, n <= 200
- grid[i][j] is 0 or 1; there is at least one 1.
Examples
Example 1
Input
grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output
6
Meeting at (0,2) gives total distance 6, which is minimal.
Example 2
Input
grid = [[1,1]]
Output
1
Either occupied cell yields total distance 1.