w Олимпиады по программированию

Олимпиады по программированию

olympiads.ru

Дистанционные семинары
Оглавление
Как пользоваться
Система проверки задач
Регистрация, изменение настроек
Страница сдачи решений
Результаты
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Задача 05-3. Табличка

Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте: 3 секунды

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

Формат входных данных
В первой строке входного файла содержатся два натуральных числа N и M, не превосходящих 100. Далее идут N строк по M чисел - элементы таблицы.

Формат выходных данных
Выходной файл должен содержать N строк по M чисел - элементы искомой таблицы.

Пример

input.txt output.txt
2 3
0 0 1
1 0 0
1 1 0
0 1 1