Add One Delivery Source
Asked at Amazon
AmazonReported by the problem's creator, not verified
A binary grid marks delivery points: a cell holding 1 is a source, a cell holding 0 is an ordinary cell. Movement is allowed in all eight directions (horizontal, vertical and diagonal) and every step costs 1, so the distance between (r1, c1) and (r2, c2) is max(abs(r1 - r2), abs(c1 - c2)).
The inconvenience of a cell is its distance to the nearest source. The inconvenience of the grid is the largest inconvenience over all cells.
Examples
Example 1
Input: grid =
[[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0]]Output:
5Explanation: The grid has no source, so the new one is the only one. Placing it in column 4 or 5 of the middle row leaves the farthest column 5 steps away and every row within 1, so the best possible inconvenience is 5.