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

Соревнование школьников. Октябрь 2001

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

F. Филиалы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
СКБ Контур имеет множество филиалов, разбросанных по всему городу. Из-за их многочисленности клиенты часто путаются и не знают, куда им идти. Естественно, это недопустимо, поэтому руководство СКБ Контур решило создать справочник, который поможет клиентам выбрать именно то, что им нужно. Вам предстоит помочь нам в этом нелёгком деле.
Город представлен в виде сетки кварталов. Каждый квартал представляет собой квадрат, стороны которого являются улицами, а углы - перекрёстками. Будем считать, что все заведения, в том числе и филиалы СКБ Контур находятся именно на перекрёстках. Филиалы СКБ Контур бывают разного типа, например: сервисные центры, склады, магазины, учебные центры и т.д. Но, в принципе, в каждом из этих подразделений есть сотрудники по работе с клиентами, которые смогут дать всю необходимую информацию, поэтому нам будет достаточно для каждого перекрёстка в городе указать ближайшее подразделение СКБ Контур (или подразделения, если их несколько).
Такова наша задача, но мы не будем выполнять её всю. Как и полагается в индустрии программирования, мы сначала сделаем урезанный, отладочный вариант программы, который будет генерировать лишь часть информации, а именно: наша программа будет выдавать только типы ближайших подразделений.
Сервисные центры обозначим числом 1, склады — 2, магазины — 4, учебные центры — 8, и т.д. Всего различных типов подразделений будет не больше 11. Каждому перекрёстку назначим число, равное сумме обозначений типов подразделений, находящихся на данном перекрёстке (заметим, что на одном перекрёстке не может быть нескольких подразделений одного типа. Перекрёстки, на которых не находится ни одного подразделения СКБ Контур, обозначим числом 0.
Problem illustration
Расстояние будем измерять количеством отрезков улиц, которые нам нужно пройти (см. рисунок). Например, расстояние от одного угла квартала до противоположного равно двум. От нас требуется найти для каждого перекрёстка, на котором не находится подразделений СКБ Контур, число равное сумме обозначений типов ближайших подразделений. Например, если на расстоянии 1 от данного перекрёстка нет подразделений СКБ Контур, на расстоянии 2 — подразделение типа 16, на расстоянии 2 (в другом направлении) — два подразделения типа 8 и одно подразделение 4, и больше нет подразделений на расстоянии 2, то данный перекрёсток надо обозначить числом 28 = 16 + 8 + 4. Подразделения, удалённые дальше, чем на 5 от данного перекрёстка, мы не рассматриваем. Таким образом, если для данного перекрёстка нет подразделений СКБ Контур находящихся ближе, чем в 6 кварталах, то мы обозначим его числом 0.

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

В первой строке содержатся целые числа H и W в пределах от 1 до 150 — количество улиц "по вертикали" и "по горизонтали" соответственно. Затем идёт H строк по W чисел в каждой, где i-е число в j-й строке описывает типы подразделений на перекрёстке i-й "вертикальной" улицы и j-й "горизонтальной".

Результат

Вы должны выдать H строк по W чисел в каждой, где i-е число в j-й строке будет равно сумме обозначений типов самых близких подразделений, если на перекрёстке i-й "вертикальной" улицы и j-й "горизонтальной" нет подразделений СКБ Контур, и −1 в противном случае.

Пример

исходные данныерезультат
5 5
0 0 2 0 2
0 0 0 0 0
0 0 0 0 0
0 0 0 5 0
1 0 0 4 0
2 2 -1 2 -1
3 2 2 7 2
1 7 7 5 7
1 5 5 -1 5
-1 1 4 -1 4
Автор задачи: Леонид Волков, Александр Сомов
Источник задачи: USU Open Collegiate Programming Contest October'2001 Junior Session
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1121. Филиалы