e-olymp
Competitions

Ukrainian Olympiad in Informatics, III Stage, II Round

Казак Ус и матрица

Казак Ус получил матрицу $a$ размером $n$ на $m$ (т.е. матрица с $n$ строк и $m$ столбиков). Элементами этой матрицы являются только нули и единицы. Казаку рассказали о манхэттенском расстоянии между элементами матрицы. Оказывается, что если один элемент матрицы находится в строке под номером $i$ и столбце под номером $j$, а другой элемент находится в строке $p$ и столбце $k$, то манхэттенским расстоянием между этими элементами считается число $\mid i - p \mid + \mid j - k \mid$ (сумма модулей разностей координат элементов в матрице). После этого Ус понял, что <<красотой>> любого элемента матрицы называют расстояние от этого элемента до ближайшего элемента, который является единицей. Заметьте, что <<красота>> любой единицы равна $0$. К тому же Козак узнал, что в таких матрицах обязательно есть хотя бы одна единица. Ваша задача несложная --- найдите <<красоту>> наиболее <<красивого>> элемента матрицы. \InputFile Первая строка содержит два целых числа $ $ и $m$ $(1 \leq n,m \leq 20)$ --- количество строк и столбцов в матрице. Каждая из следующих $n$ строк содержит $m$ цифр $a_{i,1}, a_{i,2},...,a_{i,m}$ $(0 \leq a_{i,j} \leq 1)$ --- значения элементов матрицы. Гарантируется, что присутствует хотя бы одна единица. \OutputFile Выведите одно число --- максимальную <<красоту>>. \Note Для матрицы из первого примера запишем <<красоту>> каждого ее элемента в матрицу: \begin{center} 1 0 1 2 1 2 \end{center} Как мы видим, сразу два элемента матрицы --- (вторая строка, первый столбец), и (вторая строка, третий столбик) имеют наибольшую <<красоту>> --- 2. Для второго примера матрица <<красоты>>: \begin{center} 1 0 1 0 2 1 1 0 3 2 2 1 \end{center} \Scoring Решения, которые работают правильно для ограничений $n = 1$, наберут по крайней мере $30$ баллов. Решения, которые работают правильно для ограничений $n = 2$, наберут по крайней мере $30$ баллов.
Time limit 1 second
Memory limit 256 MiB
Input example #1
2 3
010
000
Output example #1
2
Input example #2
3 4
0101
0001
0000
Output example #2
3
Author Mark Grishechkin