Казак Ус и матрица
Казак Ус и матрица
Казак Ус получил матрицу a размером n на m (т.е. матрица с n строк и m столбиков). Элементами этой матрицы являются только нули и единицы.
Казаку рассказали о манхэттенском расстоянии между элементами матрицы. Оказывается, что если один элемент матрицы находится в строке под номером i и столбце под номером j, а другой элемент находится в строке p и столбце k, то манхэттенским расстоянием между этими элементами считается число \mid i - p \mid + \mid j - k \mid (сумма модулей разностей координат элементов в матрице).
После этого Ус понял, что «красотой» любого элемента матрицы называют расстояние от этого элемента до ближайшего элемента, который является единицей. Заметьте, что «красота» любой единицы равна 0. К тому же Козак узнал, что в таких матрицах обязательно есть хотя бы одна единица.
Ваша задача несложная — найдите «красоту» наиболее «красивого» элемента матрицы.
Input data
Первая строка содержит два целых числа и 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) — значения элементов матрицы.
Гарантируется, что присутствует хотя бы одна единица.
Output data
Выведите одно число — максимальную «красоту».
Examples
2 3 010 000
2
3 4 0101 0001 0000
3
Note
Для матрицы из первого примера запишем «красоту» каждого ее элемента в матрицу:
1 0 1
2 1 2
Как мы видим, сразу два элемента матрицы — (вторая строка, первый столбец), и (вторая строка, третий столбик) имеют наибольшую «красоту» — 2.
Для второго примера матрица «красоты»:
1 0 1 0
2 1 1 0
3 2 2 1
Scoring
Решения, которые работают правильно для ограничений n = 1, наберут по крайней мере 30 баллов.
Решения, которые работают правильно для ограничений n = 2, наберут по крайней мере 30 баллов.