Shortest Distance to an Artifact

You are given a grid represented as a matrix with (m) rows and (n) columns. Each cell in the grid is either empty (denoted as 0) or contains an artifact (denoted as 1). An intruder can enter the building from any empty cell and moves in four directions (up, down, left, right) to reach an artifact. Your task is to compute the minimum number of moves the intruder must make to reach the closest artifact from any empty cell.

Mathematically, if we denote the Manhattan distance between two cells ((i,j)) and ((k,l)) by (d((i,j), (k,l)) = |i-k| + |j-l|), then you are required to find:

[ \min_{(i,j) \text{ s.t. } matrix[i][j]=0} \left( \min_{(k,l) \text{ s.t. } matrix[k][l]=1} d((i,j), (k,l)) \right) ]

If there is no empty cell or no artifact such that the distance can be computed, output (-1).

inputFormat

The input is read from standard input (stdin). The first line contains two integers (m) and (n), representing the number of rows and columns respectively. The following (m) lines each contain (n) space-separated integers (each either 0 or 1) representing the grid.

outputFormat

Output a single integer representing the minimum number of moves required. If it is not possible to compute a valid distance (i.e. if there are no artifacts or no empty cells), output (-1).## sample

4 4
0 1 0 0
0 0 0 1
0 0 0 0
1 0 0 0

1