ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2155. Квадрокоптер

Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ
В компании NAUMEN проводится тестирование новейшего ПО для квадрокоптеров. Вове, работающему в NAUMEN, было поручено запустить квадрокоптер на клетчатом поле. Но вот беда — подул сильный ветер, и квадрокоптер стал неуправляемым! Вове нужно как можно быстрее его поймать.
Клетчатое поле имеет h рядов, пронумерованных от 1 до h, и w столбцов, пронумерованных от 1 до w. Каждая клетка имеет болотистость (целое число от 1 до 999 999) и направление ветра (одно из четырёх: вверх, вниз, влево или вправо).
Вова начинает в клетке в ряду r1 и столбце c1 и ходит по полю как хочет. Он может переместиться на клетку, имеющую общую сторону с его текущей клеткой, на это у него уходит количество секунд, равное болотистости клетки, куда он хочет переместиться. Более формально, чтобы переместиться на соседнюю клетку с болотистостью x, Вова ждёт x секунд, после чего моментально переходит на выбранную клетку. Выходить за пределы поля Вова не может. Вова также может решить никуда не ходить, а стоять на текущей клетке в течение произвольного количества времени.
Квадрокоптер начинает в клетке в ряду r2 и столбце c2 и перемещается по направлению ветра со скоростью 1 клетка в секунду. Более формально, по прошествии каждой секунды квадрокоптер моментально перелетает на соседнюю клетку в направлении ветра. Направление вверх соответствует уменьшению номера ряда, вниз — увеличению номера ряда, влево — уменьшению номера столбца, вправо — увеличению номера столбца. Если ветер в текущей клетке направлен за пределы поля, то квадрокоптер улетает с поля, после чего его нельзя поймать.
Как только Вова окажется в одной клетке с квадрокоптером, Вова сможет поймать его. При этом если Вова оказывается в клетке в тот же момент, когда квадрокоптер улетает с этой клетки, Вове не удаётся его поймать. Определите, сможет ли Вова поймать квадрокоптер, и если да, то найдите наименьшее возможное количество секунд, за которое он сможет это сделать.

Исходные данные

В первой строке через пробел заданы два целых числа h и w — высота и ширина поля (1 ≤ h, w ≤ 250; w · h ≠ 1).
Во второй строке через пробел заданы два целых числа r1 и c1 — начальное положение Вовы (1 ≤ r1h; 1 ≤ c1w).
В третьей строке через пробел заданы два целых числа r2 и c2 — начальное положение квадрокоптера (1 ≤ r2h; 1 ≤ c2w). Гарантируется, что Вова и квадрокоптер начинают в разных клетках.
Далее идут h строк, задающих болотистость клеток. В i-й из них через пробел заданы w чисел от 1 до 999 999 включительно; j-е из чисел равно болотистости клетки в ряду i в столбце j.
Далее идут h строк, задающих направление ветра в клетках. В i-й из них даны w заглавных букв «U», «D», «L» или «R», не разделённых пробелом; j-й из символов соответствует направлению ветра в ряду i в столбце j. Символ «U» означает направление вверх, «D» — вниз, «L» — влево, «R» — вправо.

Результат

Если Вова не сможет поймать квадрокоптер, выведите единственное число −1. Иначе, выведите наименьшее возможное количество секунд, за которое Вова сможет поймать квадрокоптер.

Примеры

исходные данныерезультат
2 7
1 1
1 4
1 1 1 1 1 1 1
1 1 1 1 1 1 1
RDRDRDR
URURURU
7
2 6
1 1
1 4
1 1 1 1 1 1
1 1 1 1 1 1
RDRDRD
URURUR
-1
3 3
2 2
1 1
8 9 8
8 8 8
8 8 8
RRD
URD
ULL
9
Автор задачи: Валентин Зуев