eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Казак Ус получил матрицу $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$ баллов.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
2 3
010
000
Çıxış verilənləri #1
2
Giriş verilənləri #2
3 4
0101
0001
0000
Çıxış verilənləri #2
3
Müəllif Mark Grishechkin