Козак Вус та матриця#10354
Козак Вус отримав матрицю розміром на (тобто матриця з рядків та стовпчиків). Елементами цієї матриці були лише нулі та одиниці.
Козаку розповіли про манхеттенську відстань між елементами матриці. Виявляється, що якщо один елемент матриці знаходиться в рядку під номером та стовпчику під номером , а інший елемент знаходиться в рядку та стовпчику , то манхеттенською відстанню між цими елементами вважається число \mid i - p \mid + \mid j - k \mid (сума модулів різниць координат елементів в матриці).
Після цього Вус зрозумів, що «красою» будь-якого елементу матриці називають відстань від цього елементу до найближчого елемента, який є одиницею. Зауважте, що «краса» будь-якої одиниці рівна . До того ж Козак дізнався, що у таких матрицях обов'язково є хоча б одна одиниця.
Ваша задача нескладна — знайдіть «красу» найбільш «красивого» елементу матриці.
Перший рядок містить два цілі числа та (1 \leq n,m \leq 20) — кількість рядків та стовпчиків у матриці.
Кожен з наступних рядків містить цифр a_{i,1}, a_{i,2},...,a_{i,m} (0 \leq a_{i,j} \leq 1) — значення елементів матриці.
Гарантується, що буде принаймні одна одиниця.
Виведіть єдине число — максимальну «красу».
Приклад 1
Приклад 2
Для матриці з першого прикладу запишемо «красу» кожного з елементів у матрицю:
1 0 1
2 1 2
Як ми бачимо, одразу два елементи матриці — (другий рядок, перший стовпчик), та (другий рядок, третій стовпчик) мають найбільшу «красу» — 2.
Для другого прикладу матриця «краси»:
1 0 1 0
2 1 1 0
3 2 2 1
Рішення, які працюють правильно для обмежень n = 1, набиратимуть принаймні балів.
Рішення, які працюють правильно для обмежень n = 2, набиратимуть принаймні балів.