Minimum Coverage Radius After Building One Fountain

Instructions

You are given an n x m integer matrix grid where each cell is either 0 or 1:

• grid[i][j] == 1 means the cell contains a water fountain.
• grid[i][j] == 0 means the cell is empty.

The distance between two cells (r1, c1) and (r2, c2) is the Chebyshev distance

dist = max(|r1 - r2|, |c1 - c2|)

so a diagonal step counts as distance 1, not 2.

The inconvenience of the grid (its coverage radius) is the maximum, over all empty cells, of the distance from that cell to its nearest fountain. If there are no empty cells, the inconvenience is 0.

You may choose at most one empty cell and build a fountain on it, changing that 0 to a 1.

Return the minimum possible inconvenience after doing so. The grid may contain no fountains at all; in that case you must build one.

Example 1:

Input:  grid = [[0,0,0],
                [0,0,0],
                [0,0,1]]
Output: 1

Explanation: The only fountain is at (2, 2), so cell (0, 0) is at distance max(2, 2) = 2 and the current inconvenience is 2. Building a fountain at (1, 1) puts every empty cell within distance 1 (the corners are one diagonal step away), and no choice does better, so the answer is 1.

Example 2:

Input:  grid = [[0,0,0,0,1]]
Output: 1

Explanation: The current inconvenience is 4, from cell (0, 0). Building a fountain at (0, 1) puts cells (0, 0) and (0, 2) within distance 1, while (0, 3) is already within distance 1 of the fountain at (0, 4). The answer is 1.

Example 3:

Input:  grid = [[0,0,0,1],
                [0,0,0,1]]
Output: 1

Explanation: Cells in column 2 are already within distance 1 of a fountain. Building at (0, 1) covers columns 0 through 2 of both rows within distance 1.

Constraints:

• n == grid.length
• m == grid[i].length
• 1 <= n, m <= 500
• grid[i][j] is either 0 or 1.

Function Signature

Result will appear here after submission.