Департамент образования г.Москвы
МГУ им.М.В.Ломоносова
МИОО
МЦНМО

Московская олимпиада по информатике

на сайте www.olympiads.ru

Новости Об олимпиаде Личная олимпиада Командный тур Пробный интернет-тур Заочный тур Сборы Странички других лет www.olympiads.ru
Заочный тур
Информация о заочном туре
Задачи
Тесты, решения жюри
Результаты
Регистрация, изменение настроек
Страница сдачи решений
Несколько советов участникам олимпиад
FAQ по работе с тестирующей системой
Задать вопрос оргкомитету

Московская городская олимпиада школьников по информатике, 2003/04 учебный год
при поддержке компаний
Microsoft NIX

Задача H. "Левый" лабиринт

Имя входного файла: h.in
Имя выходного файла: h.out
Максимальное время работы на одном тесте: 3 секунды
Максимальный объем используемой памяти: 8 мегабайт

В спортзале размером NxM метров построили современный аттракцион под названием "Левый лабиринт". Для этого на полу спортзала с интервалом в 1 метр начертили линии, параллельные стенам спортзала. Таким образом, спортзал разбили на NxM клеток. Дальше некоторые из этих клеток покрасили в черный цвет.

Аттракцион заключается в том, что участника ставят в некоторой клетке спортзала и просят как можно быстрее добежать до некоторой другой клетки. При этом накладываются следующие условия:

  • Участнику запрещено ходить по черным клеткам.
  • Придя в какую-то клетку, участник может пойти либо прямо, либо налево, либо направо (если в соответствующем направлении клетка не покрашена в черный цвет): ходить назад, а также ходить по диагонали запрещается.
  • За все время пути участнику разрешается повернуть направо (то есть пойти из текущей клетки направо относительно того, откуда он пришел в данную клетку) не более K раз.
  • В начальной клетке участник может встать лицом в ту сторону, в какую ему захочется. С какой стороны участник прибежит в конечную клетку также не важно.

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

Формат входных данных

Во входном файле сначала записано число K - количество разрешенных поворотов направо (целое число из диапазона от 0 до 5), затем записаны числа N и M, задающие размеры спортзала - натуральные числа, не превышающие 20. Далее записано N строк по M чисел в каждой. Число 0 обозначает непокрашенную клетку, число 1 - покрашенную, число 2 - клетку, откуда стартует участник и число 3 - клетку, куда нужно добежать (клетки, помеченные 2 и 3 являются непокрашенными). В лабиринте всегда есть ровно одна начальная клетка и ровно одна клетка, в которую нужно попасть.

Формат выходных данных

В выходной файл выведите минимальное время, за которое можно добраться в конечную клетку. Если попасть в конечную клетку с соблюдением всех условий нельзя, выведите -1.

Примеры

h.in h.out
1 5 5
2 0 0 1 1
0 1 0 0 1
1 1 0 0 1
0 0 0 0 1
3 1 0 0 1
12
0 3 4
2 0 0 0
1 1 1 0
3 0 0 0
-1
0 1 3
2 1 3
-1
Webmaster: webmaster@olympiads.ru