ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2013

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

F. Оптимизация игры

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
— Опять у тебя что-то не работает?
— Работает, только слишком медленно. Мне нужно постоянно искать расстояние от корабля до ближайшей базы, чтобы проверять, можно ли его туда телепортировать. И когда на карте много баз, всё это начинает ощутимо тормозить.
— А карта у тебя дискретная?
— Да. Карта — это сетка размера n × m из квадратных ячеек. И корабли, и базы могут находиться только в центре ячейки.
— Тогда можно заранее посчитать для каждой ячейки на карте расстояние от её центра до ближайшей базы.
— Верно. Надо попробовать.

Исходные данные

В первой строке даны целые числа n и m — количество строк и столбцов в сетке, образующей карту (1 ≤ n, m ≤ 1000). Далее записана матрица размера n × m из нолей и единиц. Единица означает, что в центре соответствующей ячейки расположена база, ноль — что её там нет. Гарантируется, что на карте есть хотя бы одна база и хотя бы одна свободная ячейка.

Результат

Выведите n строк по m чисел. j-е число в i-й строке должно быть равно квадрату расстояния от центра ячейки (i, j) карты до ближайшей базы (1 ≤ in; 1 ≤ jm). Числа в одной строке должны быть разделены одним пробелом.

Пример

исходные данныерезультат
3 4
1000
0000
0010
0 1 4 5 
1 2 1 2 
4 1 0 1 
Автор задачи: Идея — Илья Бушков
Источник задачи: XVII Открытый чемпионат Урала по спортивному программированию (май, 2013)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1976. Оптимизация игры