e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

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 Перший рядок містить два цілі числа $n$ та $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$ балів.
Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
2 3
010
000
Вихідні дані #1
2
Вхідні дані #2
3 4
0101
0001
0000
Вихідні дані #2
3
Автор Mark Grishechkin