Олимпиадный тренинг

Задача . D. Тесей и лабиринт

Задача

Темы: графы кратчайшие пути реализация *2000

Как известно, Тесей отправился на остров Крит, чтобы победить Минотавра. Приплыв на остров, он обнаружил лабиринт, который представляет собой прямоугольное поле размера n × m, состоящее из блоков размера 1 × 1.

В каждом блоке имеется кнопка, разворачивающая все блоки по часовой стрелке на 90 градусов. Каждый блок поворачивается вокруг своего центра, расположение блоков в таблице при этом не меняется. Помимо кнопки, в каждом блоке есть несколько (возможно, 0) дверей. За одну минуту Тесей может либо перейти в соседний по стороне блок, либо нажать кнопку и привести в действие механизм по повороту всех блоков по часовой стрелке на 90 градусов. Из блока A можно перейти в соседний блок B тогда и только тогда, когда у блока A есть дверь, ведущая в блок B, а у блока B есть дверь, ведущая в блок A. Тесей уже обнаружил вход в лабиринт и оказался в блоке (x_T, y_T), то есть в блоке, расположенном в ряду x_T и столбце y_T. Тесей слышал, что Минотавр прячется в блоке (x_M, y_M), и хочет узнать минимальное количество минут, через которое он сможет добраться до чудовища.

Герою не к лицу решать задачи по программированию, поэтому он просит вас помочь ему.

Входные данные

В первой строке входных данных следуют два числа n и m (1 ≤ n, m ≤ 1000) — количество строк и столбцов в лабиринте соответственно.

В каждой из последующих n строк содержится по m символов, описывающих соответствующий ряд лабиринта. Рассмотрим возможные варианты символов:

«+» означает, что этот блок имеет 4 двери (в каждый из соседних блоков);
«-» означает, что этот блок имеет 2 двери — в соседний слева и соседний справа блок;
«|» означает, что этот блок имеет 2 двери — в соседний сверху и снизу блоки;
«^» означает, что этот блок имеет 1 дверь — в соседний сверху блок;
«>» означает, что этот блок имеет 1 дверь — в соседний справа блок;
«<» означает, что этот блок имеет 1 дверь — в соседний слева блок;
«v» означает, что этот блок имеет 1 дверь — в соседний снизу блок;
«L» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний слева блок;
«R» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний справа блок;
«U» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний сверху блок;
«D» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний снизу блок;
«*» означает, что этот блок является стеной и не имеет дверей.

Лево, право, верх и низ определяются из представления лабиринта в виде таблицы, где строки пронумерованы сверху вниз от 1 до n, а столбцы слева направо от 1 до m.

В предпоследней строке содержатся два целых числа — координаты блока (x_T, y_T) (1 ≤ x_T ≤ n, 1 ≤ y_T ≤ m), где находится Тесей.

В последней строке содержатся два целых числа — координаты блока (x_M, y_M) (1 ≤ x_M ≤ n, 1 ≤ y_M ≤ m), где расположен Минотавр.

Гарантируется, что блок, в котором находится Минотавр (а также блок, в котором находится Тесей), не является блоком-стеной. Блоки, в которых изначально находятся Минотавр и Тесей, могут совпадать.

Выходные данные

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

Примечание

В момент времени 0 Тесей уже находится в лабиринте в блоке с координатами (x_T, y_T).

Примеры

№	Входные данные	Выходные данные
1	2 2 +* *U 1 1 2 2	-1
2	2 3 <>< ><> 1 1 2 1	4

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет