Дана таблица, состоящая из
N строк и
M столбцов. В каждой клетке таблицы записано одно из чисел:
0 или
1. Расстоянием между клетками
(x1, y1) и
(x2, y2) назовем сумму
|x1-x2|+|y1-y2|. Вам необходимо построить таблицу, в клетке
(i, j) которой будет записано минимальное расстояние между клеткой
(i, j) начальной таблицы и клеткой, в которой записана
1. Гарантируется, что хотя бы одна
1 в таблице есть.
Формат входных данных
В первой строке вводятся два натуральных числа
N и
M, не превосходящих 500. Далее идут
N строк по
M чисел - элементы таблицы.
Формат выходных данных
Требуется вывести
N строк по
M чисел - элементы искомой таблицы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
0 0 1
1 0 0
|
1 1 0
0 1 1
|