После столь обильного поедания фруктов на кухне Фермера Джона, Беси посетили странные мечты. Она попала в лабиринт в форме решётки клеток \(N \times M\) (\(1 \le N, M \le 1,000\)). Она начинает в левой верхней клетке и хочет попасть в правую нижнюю. Когда она стоит в клетке, он может шагнуть в любом из четырёх направлений (вверх, вниз, вправо, вверх).
Однако подождите! Каждая клетка имеет свой цвет, и каждый цвет имеет различные свойства:
-
Если клетка red (красная), то в неё ходить нельзя
-
Если клетка pink (розовая), то в неё можно ходить
-
Если клетка orange (оранжевая), то в неё можно ходить, но Беси станет пахнуть как апельсин.
-
Если клетка blue (синяя) , то она содержит пираний, которые позволят Беси пройти только если она пахнет как апельсин.
-
Если клетка purple (пурпурная), то Беси проскальзывает в следующую клетку в этом направлении (если только в следующую клетку можно заходить). Если следующая клетка также пурпурная, Беси продолжает скользить, пока не попадёт в не пурпурную клетку или остановится перед непроходимой клеткой. Скольжение одной клетки засчитывается как один шаг. Пурпурные клетки также удаляют запах.
(Пример ниже подробнее поясняет "пурпурные" клетки)
Помогите Беси добраться из левого верхнего угла в правый нижний за минимально возможное количество ходов.
ФОРМАТ ВВОДА (файл dream.in):
Первая строка ввода содержит два целых числа
\(N\) и
\(M\), представляющие количество строк и столбцов лабиринта.
Каждая из следующих \(N\) строк имеет по \(M\) целых чисел, представляющих лабиринт:
-
Целое число '0' это красная клетка
-
Целое число '1' это розовая клетка
-
Целое число '2' это оранжевая клетка
-
Целое число '3' это синяя клетка
-
Целое число '4' это пурпурная клетка
Левая-верхняя и правая-нижняя клетки всегда будут '1'.
ФОРМАТ ВЫВОДА (файл dream.out):
Одно целое число, представляющее минимальное количество ходов, которое
должна использовать Беси, чтобы пройти лабиринт, или -1, если невозможно пройти.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 0 2 1
1 1 4 1
1 0 4 0
1 3 1 1
|
10
|