Задача №162. Табличка
Обходы, определение предков и потомков, поиск цикла, компоненты слабой и сильной связности, топологическая сортировка, определение двудольности графа, мосты и точки сочленения
| Максимальное время работы на одном тесте: | 1 секунда |
Дана таблица, состоящая из 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 чисел - элементы искомой таблицы.
Примеры
Входные данные
2 3 0 0 1 1 0 0
Выходные данные
1 1 0 0 1 1
Сдать: для сдачи задач необходимо войти в систему