Сон Бессі#11162
Після того як Бессі, корова фермера Джона, з'їла забагато фруктів на кухні фермера Джона, їй почали снитися дуже дивні сни! У своєму останньому сні вона опинилася в пастці лабіринту, що має форму сітки з плиток розміру n \times m. Вона починає свій шлях у верхній лівій плитці і хоче дістатися до нижньої правої плитки. Перебуваючи на плитці, вона потенційно може перейти на сусідню плитку в будь-якому з чотирьох основних напрямків.
Але зачекайте! Кожна плитка має свій колір, і кожен колір має особливу властивість! Від однієї думки про це у Бессі починає боліти голова:
Якщо плитка червона, то вона непрохідна.
Якщо плитка рожева, то по ній можна вільно ходити.
Якщо плитка помаранчева, то по ній можна вільно ходити, але після цього Бессі починає пахнути апельсинами.
Якщо плитка синя, то в ній знаходяться піраньї, які дозволять Бессі пройти лише в тому випадку, якщо від неї пахне апельсинами.
Якщо плитка фіолетова, то Бессі буде ковзати до наступної плитки у обраному напрямку (якщо тільки вона не може пройти через неї). Якщо ця плитка також фіолетова, то Бессі продовжить ковзати, доки не зупиниться на нефіолетовій плитці або не наштовхнеться на непрохідну плитку. Проходження через одну плитку під час ковзання вважається одним ходом. Фіолетові плитки також усувають запах апельсинів у Бессі.
Допоможіть Бессі дістатися з верхньої лівої плитки до нижньої правої за мінімальну кількість ходів.
У першому рядку знаходяться два цілих числа і m~(1 \le n, m \le 1000), що позначають кількість рядків і стовпців лабіринту.
У наступних рядках знаходяться по цілих чисел, що описують лабіринт:
Число позначає червону плитку.
Число позначає рожеву плитку.
Число позначає помаранчеву плитку.
Число позначає синю плитку.
Число позначає фіолетову плитку.
У верхній лівій та нижній правій плитках завжди буде знаходитися число .
Виведіть одне ціле число, що позначає мінімальну кількість ходів, яку повинна зробити Бессі, щоб пройти лабіринт, або , якщо зробити це неможливо.
Якщо ви не до кінця розумієте, як працюють фіолетові плитки, наведений нижче приклад ілюструє їхню поведінку.
У цьому прикладі Бессі проходить одну клітинку вниз і дві клітинки вправо, а потім ковзає ще на одну клітинку вправо. Потім вона проходить одну клітинку вгору, одну клітинку вліво і одну клітинку вниз, ковзаючи ще на дві клітинки вниз. Наприкінці вона проходить ще одну клітинку вправо. Загалом це складає ходів (DRRRULDDDR).
Приклад 1