Amazon has multiple delivery centers all over the world. A city is given in the form of a grid where the delivery centers are marked as 1 and all other places are marked as 0. Distance between two cells is defined as the maximum absolute distance between x-coordinates and y-coordinates.
For example, the distance between (1, 2) and (0, 4) is max(|1 - 0|, |2 - 4|) = 2.
The inconvenience of the grid is defined as the maximum distance of any place marked 0 from its nearest delivery center.
Amazon is planning to open a new delivery center to reduce the inconvenience of the grid.
Minimize the inconvenience of the grid by converting at most one 0 (any place) to 1 (a delivery center) and report this minimum value.
Complete the function getMinInconvenience(grid).
Function Description
Complete the function getMinInconvenience in the editor below.
getMinInconvenience has the following parameter:
int grid[n][m]: 2D binary matrix
Returns
int: the minimum inconvenience possible
Constraints
1 <= n, m <= 5000 <= grid[i][j] <= 1
这道 Amazon OA 题本质上是在一个二进制网格中，先用多源 BFS 计算每个位置到最近配送中心（1）的最短距离（距离定义为切比雪夫距离，即 <code>max(|dx|, |dy|)</code>），再二分答案判断“是否能通过新增 1 个配送中心把所有 0 的最远距离压到 R 以内”。判定时只需要收集所有距离大于 R 的格子，并检查这些格子是否能被某个新增中心同时覆盖；如果可行则继续缩小 R，不可行则增大 R。整体思路是“多源 BFS + 二分 + 可行性检查”，适合 <code>n,m ≤ 500</code> 的规模。
