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

Вузовско-академическая олимпиада по информатике 2019

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

C. Пережить потоп

Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ
Любой заяц с детства знает, что делать, если случился потоп: нужно забраться выше уровня воды и ждать Мазая. Но когда потоп в самом деле случается, у зайцев начинается паника, и они не справляются с первым пунктом. Поэтому Вам поручено разобрать гипотетический случай потопа и составить план эвакуации.
Опишем гипотетический случай потопа как игру между гипотетическим зайцем и гипотетической водой. Игра происходит на клетчатом поле из n строк и m столбцов. Будем говорить, что клетка, стоящая в строке i в столбце j, имеет координаты (i, j). Известно, что при всех 1 ≤ in, 1 ≤ jm клетка с координатами (i, j) имеет высоту hij. Заяц начинает в клетке с координатами (r1, c1), вода — в клетке с координатами (r2, c2). Кроме того, заяц имеет характеристику, называемую высотой прыжка.
Заяц и вода ходят по очереди, первым ходит заяц. Каждый свой ход Заяц либо остается на месте, либо перепрыгивает в одну из соседних по стороне клеток, при этом он не может прыгнуть на клетку, высота которой превосходит высоту текущей клетки более, чем на высоту прыжка зайца. Вода же каждый свой ход попросту заполняет все клетки, имеющие заполненную водой соседнюю клетку не меньшей высоты. Выходить за пределы поля ни зайцу, ни воде нельзя.
Заяц хочет никогда не находиться в одной клетке с водой. Игра идет бесконечно долго. Определите, какой наименьшей высоты прыжка зайца достаточно, чтобы никогда не находиться в заполненной водой клетке.

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

В первой строке находятся два целых числа n и m, разделённые пробелом (1 ≤ n, m ≤ 100, n · m1 ) — размер поля.
Следующие n строк описывают поле. В каждой из n строк содержится m чисел, разделённых пробелом hij (0 ≤ hij ≤ 105) — высоты клеток.
В следующей строке находятся числа r1 и c1, разделённые пробелом (1 ≤ r1n, 1 ≤ c1m) — начальное положение зайца.
В последней строке находятся числа r2 и c2, разделённые пробелом (1 ≤ r2n, 1 ≤ c2m) — начальное положение воды.
Гарантируется, что заяц и вода начинают в разных клетках. Столбцы нумеруются от 1 до m слева направо, строки — от 1 до n сверху вниз.

Результат

Если заяц попадет в воду при любой высоте прыжка, в единственной строке выведите -1.
Иначе, в единственной строке выведите одно целое число — наименьшую высоту прыжка, при которой заяц никогда не попадет в воду при оптимальной игре.

Примеры

исходные данныерезультат
2 3
6 5 4
1 2 3
2 1
1 3
3
1 3
0 0 0
1 1
1 3
-1
Автор задачи: Антон Липин
Источник задачи: Вузовско-академическая олимпиада по информатике 2019
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2113. Пережить потоп