Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1302. Путешествие кузнечика-2
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 09/01/2003 | Областная олимпиада школьников по информатике (личное первенство, 2 лига) (4) |
| 22/10/2011 | Занятие 4 (C) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Юный энтомолог изучает уровень интеллекта кузнечика, используя специальный полигон.
Прямоугольный полигон был разделен на клетки размером 10x10 см и в каждой клетке был поставлен столбик из кубиков.
Столбик может содержать от 0 до 9 кубиков. Все кубики имеют размер стороны 10 см.
Кузнечик прыгает по следующим правилам. Кузнечик может прыгать только в направлениях, параллельных стенам полигона.
Перед прыжком он становится точно в центр верхней грани столбика из кубиков и прыгает вертикально вверх на 20 см.
Затем он планирует, используя крылья, в выбранном направлении, теряя по 10 см высоты на 10 см горизонтального полета.
В любой момент он также может сложить крылья и спикировать вертикально вниз, как показано на рис. 1.
Кузнечик не может пробивать кубики, поэтому, чтобы попасть с левого столбика на правый на рис. 2, ему потребуется два прыжка.
Кузнечик не может также покинуть полигон.
Напишите программу, которая определит наименьшее число прыжков, требующееся кузнечику, чтобы добраться до заданной клетки.
Во входном файле в первой строке содержатся два целых числа `N` и `M` через пробел – размеры полигона в клетках
(`1\ <\ N\ ≤\ 100`, `1\ <\ M\ ≤\ 100`). Во второй строке содержатся два целых числа `X_1` и `Y_1` через пробел – координаты
начальной клетки (`1\ ≤\ X_1\ ≤\ N`, `1\ ≤\ Y_1\ ≤\ M`). В третьей строке содержатся два целых
числа `X_2` и `Y_2` через пробел – координаты конечной клетки (`1\ ≤\ X_2\ ≤\ N`, `1\ ≤\ Y_2\ ≤\ M`).
Далее следует `M` строк, содержащих по `N` целых чисел от 0 до 9, разделенных пробелами – высота
столбика из кубиков в соответствующей клетке на полигоне. Первое число первой строки соответствует
координате `(1,1)`, а последнее число последней строки – координате `(N,M)`.
В выходной файл в первой строке вывести целое число `K` – минимальное количество прыжков, которое потребуется
кузнечику, чтобы добраться от начальной клетки до конечной.
Если добраться до конечной клетки невозможно, то вывести сообщение "IMPOSSIBLE" без кавычек.
Пример ввода
3 3 2 1 3 3 3 0 3 2 0 4 1 0 5
Пример вывода
7
