Maximum Manhattan Distance to a Building

You are given a grid representing a city with m rows and n columns. Each cell in this grid is either empty (denoted by 0) or contains a building (denoted by 1). Your task is to choose an empty cell (with a value of 0) to construct a new building such that the Manhattan distance from this cell to the nearest existing building is maximized.

The Manhattan distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is given by: \[ |x_1 - x_2| + |y_1 - y_2| \]

If there is no suitable empty cell or if there are no buildings on the grid, output -1.

Note: The input is read from standard input (stdin) and the output is printed to standard output (stdout).

inputFormat

The first line of the input contains two integers m and n separated by a space, denoting the number of rows and columns respectively.

The next m lines each contain n space-separated integers (either 0 or 1) describing the grid.

outputFormat

Output a single integer which is the maximum Manhattan distance from an empty cell to its nearest building. If no valid placement exists or there are no buildings, output -1.

3 3
1 0 0
0 0 0
0 0 1

2