Company: Amazon_31july
Difficulty: medium
Minimize Grid Inconvenience Problem Description 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, 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. Consider the following illustration: Input Grid: n = 2 (rows), m = 4 (columns) grid = [[0, 0, 0, 1], [0, 0, 0, 1]] Visual Representation: 0 0 0 1 0 0 0 1 Distances from each cell to the nearest delivery center (1s) are shown below. The initial