Битовая карта
Битовая карта
Задана прямоугольная битовая карта размером n \times m. Каждая точка в ней белая или черная, хотя бы одна точка белая. Точку в i-ой строке и j-ом столпце назовем пикселем (i, j). Расстояние между двумя пикселями p_1 = (i_1, j_1) и p_2 = (i_2, j_2) определяется следующим образом:
Для каждой точки найдите расстояние до ближайшей белой точки.
Giriş verilənləri
Первая строка содержит количество тестов 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) белая.
Çıxış verilənləri
В i-ой строке для каждого теста выведите m целых чисел f(i, 1), ..., f(i, m), где f(i, j) — расстояние от точки (i, j) до ближайшей белой точки.
Nümunə
1 3 4 0001 0011 0110
3 2 1 0 2 1 0 0 1 0 0 1