Amazon's getMinInconvenience OA: Chebyshev distance to the nearest delivery center, one new center allowed. Multi-source BFS, then binary search on the answer with a bounding-box test. **Distances first.** Run one multi-source BFS from every `1` at once. With all 8 neighbour moves, a BFS step count is exactly the Chebyshev distance, so after O(n·m) work `dist[r][c]` is each cell's distance to its nearest center (infinite when the grid has no center). **Binary search on the answer `K`.** `K` is achievable if one new center can come within `K` of every cell that is now farther than `K`. The cells within Chebyshev distance `K` of a cell form a square of side `2K + 1`, so the question is whether the squares around all the far cells share a point. They do exactly when the far cells' bounding box spans at most `2K` rows and at most `2K` columns. Clipping to the grid never empties that intersection, and any point in it is automatically a `0`: a center there would already be within `K` of the far cells. Feasibility only gets easier as `K` grows, so binary search between 0 and `n + m`. The reports describe this shape: BFS for the current distances, then binary search for the smallest feasible score, one checking each K by passing over the grid with the Chebyshev formula and another by bounding the far cells. The reference adds one step: it buckets cells by distance and builds the far cells' bounding box for every `K` in one sweep, so each check is O(1) instead of a fresh pass over the grid. A per-`K` scan of the grid inside the binary search, O(n·m·log(n + m)), is also fast enough at 500 × 500. **The 4-direction variant.** Use the 4 neighbour moves in the BFS. A Manhattan ball is a diamond, which becomes a square in the rotated coordinates `u = r + c`, `v = r - c`, so the same bounding-box test applies to `(u, v)`. One extra check: some real cell `(r, c)` must have `r + c` and `r - c` inside the shared ranges (parity and the grid edges can rule a range out), which the reference checks row by row.