A festival field is an m x n grid crowd. crowd[r][c] >= 0 is the number of people standing on cell (r, c); crowd[r][c] == -1 marks a pond, where nobody stands and nothing can be built. The organisers will pitch one first-aid tent on a cell that is not a pond. People walk along the grid (ponds are small enough to walk round, so distance is measured as if they were not there): a person on (r1, c1) walks |r1 - r2| + |c1 - c2| to a tent on (r2, c2).
Choose the tent cell that makes the total walking distance of everybody as small as possible. Return [total, row, col]. If several cells tie, choose the smallest row, then the smallest col.
Examples
Input: crowd = [[0, 2, 0], [3, -1, 1], [0, 2, 0]]
Output: [10, 1, 0]
Explanation: the centre would cost 8 but it is a pond. Cell (1, 0) costs
3*0 + 2*2 + 2*2 + 1*2 = 10.
Input: crowd = [[5]]
Output: [0, 0, 0]
Input: crowd = [[1, -1, 1]]
Output: [2, 0, 0]
Constraints
1 <= m, n <= 500-1 <= crowd[r][c] <= 1000, and at least one cell is not a pond.- Adding up the walk of every person for every possible cell is far too slow for the largest fields.
Goals
- Split a grid walking distance into a row part and a column part that do not interact
- Compute the cost of every row (and every column) in one sweep using running totals
- Handle the case where the individually best row and column meet on a forbidden cell