Best Starting Cell for Restaurant Distance
Problem statement
You are given a binary matrix grid. A cell containing 1 is a restaurant. Choose a starting cell that minimizes the total Manhattan distance to all restaurants.
For this exercise, any cell may be chosen, including a restaurant cell. There are no obstacles. The distance from (r, c) to (x, y) is |r - x| + |c - y|, and the objective is the sum of these distances.
Return [row, column, totalDistance] using zero-based coordinates. If several cells have the same total, choose the smallest row, then the smallest column. If there are no restaurants, return [0, 0, 0].
Function
bestStartingCell(grid: int[][]) → int[]Examples
Example 1
grid = [[1,0,0],[0,0,1],[1,0,0]]return = [1,0,4]From (1,0), the distances to restaurants (0,0), (1,2), and (2,0) are 1, 2, and 1. Their sum is 4, the minimum.
Example 2
grid = [[1,0,1],[0,0,0]]return = [0,0,2]Every cell in row 0 from column 0 through 2 has total distance 2. The tie rule selects (0,0), which is itself a restaurant.
Example 3
grid = [[0,0],[0,0]]return = [0,0,0]With no restaurants, every total is zero and the specified result is [0,0,0].
Constraints
- 1 <= grid.length <= 200
- 1 <= grid[i].length <= 200
- 0 <= grid[i][j] <= 1
- All rows have the same length.