Add One Delivery Source

AmazonHard

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.

Part 1: Add one source optimally

You are given a binary grid grid. Add exactly one more source, on any cell of your choice (a cell that already holds a 1 is allowed), and return the smallest inconvenience the grid can have afterwards.

The grid may contain no source at all before you add one; then the new source is the only one.

Example 1
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
5
Why: 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.

Constraints

1 <= len(grid) <= 200
1 <= len(grid[0]) <= 200
grid[r][c] is 0 or 1
The grid may contain no 1

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question