Cossack Vus and the Matrix#10354
Kozak Vus has a matrix of size n \times m, consisting only of zeros and ones.
The Manhattan distance between two elements in the matrix is defined as follows: if one element is at row and column , and another is at row and column , then their Manhattan distance is \mid i - p \mid + \mid j - k \mid (the sum of the absolute differences of their row and column indices).
The "beauty" of an element in the matrix is the Manhattan distance from that element to the nearest element that is a one. Note that the "beauty" of any element that is a one is zero. Additionally, it is guaranteed that the matrix contains at least one one.
Your task is to determine the "beauty" of the most "beautiful" element in the matrix.
The first line contains two integers and (1 \leq n, m \leq 20), representing the number of rows and columns in the matrix.
Each of the next lines contains digits a_{i,1}, a_{i,2}, \ldots, a_{i,m} (0 \leq a_{i,j} \leq 1), representing the elements of the matrix.
It is guaranteed that there is at least one one in the matrix.
Output a single number — the maximum "beauty" of any element in the matrix.
Example 1
Example 2
Consider the matrix from the first example, where the "beauty" of each element is:
1 0 1
2 1 2
Here, the elements at (second row, first column) and (second row, third column) have the highest "beauty" of 2.
For the second example, the "beauty" matrix is:
1 0 1 0
2 1 1 0
3 2 2 1
Solutions that correctly handle the case where n = 1 will score at least 30 points.
Solutions that correctly handle the case where n = 2 will score at least 30 points.