Optimal Firefighter Position

This problem involves finding the optimal position for a firefighter on a grid so that the maximum Manhattan distance from the chosen empty cell to any building is minimized. The grid is given as an ( m \times n ) matrix, where each cell contains either a 1 (representing a building) or a 0 (representing an empty cell). The Manhattan distance between two cells ( (i, j) ) and ( (p, q) ) is defined as ( |i - p| + |j - q| ).

For example, consider the following 3x3 grid:

1 0 1
0 0 0
1 0 1

The optimal solution is to station the firefighter at cell (1, 1), for which the farthest building is at a Manhattan distance of 2. Your task is to compute this minimized maximum distance given any valid grid.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers ( m ) and ( n ), representing the number of rows and columns of the grid.
  
• The next ( m ) lines each contain ( n ) integers (each either 0 or 1) separated by spaces, describing the grid.
  
  A 1 indicates that there is a building in that cell, and a 0 indicates that the cell is empty.

outputFormat

Output a single integer to standard output (stdout): the minimized maximum Manhattan distance from the chosen empty cell (where the firefighter is stationed) to the farthest building.## sample

3 3
1 0 1
0 0 0
1 0 1

2