|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 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 |