|
Юпитер
(Время: 1 сек. Память: 64 Мб Сложность: 62%)
На поверхности Юпитера приземлился летающий робот, его задачей является исследование поверхности планеты. Поверхность Юпитера представляет собой прямоугольное поле из N×M клеток, каждая из которых представляет лаву или твердую поверхность различной высоты. Для снятия проб грунта роботу необходимо переместиться из клетки с координатами (1,1) в клетку с координатами (X,Y). Для передвижения робот может использовать два типа действий - это переезд и перелет.
Переезд - перемещение в одну из четырех соседних клеток, имеющих общую грань с заданной, при этом высота клеток не должна отличаться больше чем на единицу.
Перелет из одной клетки в другую позволяет преодолевать препятствия, но для него нужна энергия, которая расходуется из специальных аккумуляторов, количество которых на борту ограничено и равно K. Дальность перелета ограничена мощностью одного аккумулятора и составляет D единиц. Перелет возможен только по направлениям, параллельным границам поля. Во время перелета луноход не может менять направление, но при этом может менять высоту, облетая препятствия. На каждое перемещение на одну клетку вдоль выбранного направления, вверх или вниз на одну единицу по высоте, тратится ровно одна единица энергии. После перелета аккумулятор утилизируется и больше использоваться не может, оставшаяся в нем энергия пропадает.
Одним действием назовем один переезд или один перелет. Ваша задача для заданной поверхности найти наименьшее количество действий, необходимых для достижения заданной клетки.
Входные данные
Первая строка входного файла INPUT.TXT содержит размеры поля N, M (1 ≤ N,M ≤ 100), разделенные пробелом. Во второй строке идут координаты клетки, куда необходимо найти путь X,Y (1 ≤ X ≤ N, 1 ≤ Y ≤ M). На третьей строке через пробел указаны целые K и D (0 ≤ K ≤ 10, 0 ≤ D ≤ 100). Далее в M строках идут по N чисел через пробел – высотные отметки участка Юпитера, высота каждой клетки - целое число, лежащее в диапазоне от 0 до 10000 включительно. Высота 0 (ноль) обозначает лаву, на которой останавливаться нельзя, но можно пролететь над ней.
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число - минимальное количество действий, необходимых для достижения заданной клетки. Если добраться до заданной клетки нельзя, то необходимо вывести в строке слово IMPOSSIBLE.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 4
5 3
1 6
2 1 4 2 1
1 2 4 2 1
4 4 6 2 1
2 2 2 2 1 | 5 |
| 2 | 4 4
4 2
1 3
2 0 0 3
3 0 4 3
4 0 5 2
4 5 5 1 | 3 |
| 3 | 3 3
3 3
10 10
1 0 0
1 0 0
0 1 1 | IMPOSSIBLE |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
