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

Битовая карта

Битовая карта

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Задана прямоугольная битовая карта размером 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|

Для каждой точки найдите расстояние до ближайшей белой точки.

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ə

Giriş verilənləri #1
1
3 4
0001
0011
0110
Çıxış verilənləri #1
3 2 1 0
2 1 0 0
1 0 0 1