← 返回 amazon 的题目列表Minimize the Maximum Distance to a 1 After Flipping One 0
类型：online_judge
Problem: Minimize the Maximum Distance to a 1 After Flipping at Most One 0
You are given an m x n binary matrix grid, where each cell is either 0 or 1.
You may choose at most one cell with value 0 and change it to 1.
For a remaining 0 cell, its distance is defined as the Manhattan distance to the nearest 1 cell in the matrix. You may move only up, down, left, and right, and each move has cost 1.
Return the minimum possible value of the maximum distance among all remaining 0 cells after performing at most one flip.
If there is no 0 in the matrix, return 0.
Input Format
m n
grid[0][0] grid[0][1] ... grid[0][n-1]
...
grid[m-1][0] ... grid[m-1][n-1]
Rows may also be provided as compact strings, such as 0101.
Output Format
Print one integer: the minimized maximum distance.
Constraints
1 <= m, n <= 500
m * n <= 200000
grid[i][j] is either 0 or 1
Example 1
Input:
1 5
1 0 0 0 0
Output:
1
Explanation: Flip position 3 to 1. Then every remaining 0 is within distance 1 from a 1.
Example 2
Input:
3 3
1 0 0
0 0 0
0 0 0
Output:
2
Example
Input
1 5
1 0 0 0 0
Output
1