Add One Source to Minimize Grid Inconvenience

Implement min_max_inconvenience(grid).

grid is a non-empty rectangular matrix containing 0 and 1. A cell containing 1 is an existing colored source. You may choose any one cell, including an already colored cell, and add a colored source there.

Movement is allowed in all eight directions: horizontal, vertical, and diagonal. Every move costs one. A cell's inconvenience is its shortest-path distance to the nearest colored source after your addition. Return the smallest possible value of the maximum inconvenience over all cells.

Examples

• For [[0]], return 0.
• For [[1, 0, 0]], return 1 by adding a source at the last cell.
• For [[1, 0], [0, 0]], return 1; after adding one source, at least one uncolored cell remains one move from its nearest source.

Constraints

• 1 <= len(grid), len(grid[0]) <= 200
• Every row has the same length.
• Every element is either 0 or 1.
• The grid may initially contain no colored source.

Add One Source to Minimize Grid Inconvenience

Hints

1. First compute every cell's distance to the existing sources with multi-source BFS.
2. For a proposed answer d, only cells whose old distance exceeds d must be covered by the new source.
3. An eight-direction distance-d ball is an axis-aligned square, so intersect row and column intervals.

Approach

Multi-source BFS yields existing-source distances under eight-direction movement. Binary-search the maximum allowed inconvenience d. Every cell already within d needs no help; each remaining cell requires the new source's row and column to lie within d of its own row and column. These requirements are independent interval intersections, so feasibility is constant extra work per cell. Feasibility is monotone in d.

• Time complexity: O(rows * columns * log(max(rows, columns))).
• Space complexity: O(rows * columns) for distances and the BFS queue.