P15031 [UOI 2021 II Stage] Matrix

Cossack Beard got a matrix $a$ of size $n$ by $m$ (that is, a matrix with $n$ rows and $m$ columns). The elements of this matrix are only $0$ and $1$. Someone introduced Cossack to the Manhattan distance between elements in a matrix. It turns out that if one element is in row $i$ and column $j$, and another element is in row $p$ and column $k$, then the Manhattan distance between these two elements is defined as $\mid i - p \mid + \mid j - k \mid$ (the sum of the absolute values of the coordinate differences). After that, Beard understood that the **"beauty"** of any element in the matrix is the distance from that element to the nearest element with value $1$. Note that the **"beauty"** of any $1$ is $0$. Also, Cossack learned that in such a matrix, there is at least one $1$. Your task is simple: find the **"beauty"** of the most **"beautiful"** element in the matrix.

The first line contains two integers $n$ and $m$ $(1 \leq n,m \leq 20)$, the number of rows and columns of the matrix. The next $n$ lines each contain $m$ digits $a_{i,1}, a_{i,2},...,a_{i,m}$ $(0 \leq a_{i,j} \leq 1)$, the values of the matrix elements. It is guaranteed that there is at least one $1$.

Output one number, the maximum **"beauty"**.

### Sample Explanation For the matrix in the first sample, write the **"beauty"** of each element in matrix form: :::align{center} 1 0 1 2 1 2 ::: As we can see, there are two matrix elements, (row $2$, column $1$) and (row $2$, column $3$), that have the maximum **"beauty"**, which is $2$. For the second sample, its **"beauty"** matrix is: :::align{center} 1 0 1 0 2 1 1 0 3 2 2 1 ::: ### Scoring Rules A solution that works correctly under the constraint $n = 1$ will get at least $30$ points. A solution that works correctly under the constraint $n = 2$ will get at least $30$ points. The translation was completed by DeepSeek V3. Translated by ChatGPT 5