Задачі
Битовая карта
Битовая карта
Задана прямоугольная битовая карта размером $n \times m$. Каждая точка в ней белая или черная, хотя бы одна точка белая. Точку в $i$-ой строке и $j$-ом столпце назовем пикселем $(i, j)$. Расстояние между двумя пикселями $p_1 = (i_1, j_1)$ и $p_2 = (i_2, j_2)$ определяется следующим образом:
$$
d(p_1, p_2) = |i_1~–~i_2| + |j_1~–~j_2|
$$
Для каждой точки найдите расстояние до ближайшей белой точки.
\InputFile
Первая строка содержит количество тестов $t$. Первая строка каждого теста содержит два целых числа $n, m~(1 \le n \le 1000, 1 \le m \le 1000)$. Каждая из следующих $n$ строк содержит слово из нулей и единиц длины $m$, описывая битовую карту. В $j$-ой позиции $i~(1 \le i \le n, 1 \le j \le m)$-ой строки находится $1$ если только точка $(i, j)$ белая.
\OutputFile
В $i$-ой строке для каждого теста выведите $m$ целых чисел $f(i, 1), ..., f(i, m)$, где $f(i, j)$ --- расстояние от точки $(i, j)$ до ближайшей белой точки.
Вхідні дані #1
1 3 4 0001 0011 0110
Вихідні дані #1
3 2 1 0 2 1 0 0 1 0 0 1