Staff
Best Meeting Point
Given an m x n binary grid grid, each 1 marks the home of a friend and each 0 marks an empty cell.
Choose a meeting point in the grid that minimizes the total travel distance from every friend's home to that point. The distance between two cells (r1, c1) and (r2, c2) is the Manhattan distance |r1 - r2| + |c1 - c2|.
Return the minimum possible total travel distance.
Example 1
1 0 0 0 1 0 0 0 0 0 0 0 1 0 0
Input
grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]Output
6Meeting at cell (0, 2) gives distances 2, 2, and 2 for a total of 6.
Example 2
1 1
Input
grid = [[1,1]]Output
1The two friends are adjacent, so either home can be chosen as the meeting point with total distance 1.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- grid[i][j] is 0 or 1
- There will be at least two friends in the grid