Дано клеточное поле из N строк и M столбцов. На поле есть запрещенные для движения клетки. Вы начинаете «гонку» из клетки в левом верхнем углу, а заканчиваете ее в правом нижнем. У вас есть соперник, стартовая точка и путь движения которого известны заранее (путь необязательно оптимальный). Вам предлагается за минимальное число шагов достичь финиша по следующим правилам:
Двигаться можно только в соседнюю по горизонтали или вертикали свободную клетку (одно перемещение – это переход на соседнюю клетку).
Передвижение осуществляется поочередно: сначала ходит соперник, затем вы.
Не допускаются нахождение обоих участников в одном квадрате одновременно.
Ходы соперников обязательны.
Если ходы соперника закончились, то он останавливается в последней достигнутой им клетке. Но заранее известно, что он при этом не заблокирует возможный путь до финиша. Если соперник достиг финиша, то он исчезает с поля.
Требуется написать программу подсчета минимального количества перемещений, требуемых для достижения финиша или определить, что это сделать невозможно.
Формат входных данных
В первой строке размер поля: два числа через пробел 0 < N, М ≤ 150. Далее идет N строк в каждой из которых по M символов, описывающих поле: точка (.) – клетка свободна, решетка (#) – непроходимая клетка. В следующей строке два числа – номер строки и столбца, где находится ваш соперник. Далее следует строка с описанием пути соперника: R – движение вправо, L – влево, U – вверх, D - вниз. Количество ходов соперника не более 32000.
Формат выходных данных
Содержит единственное число – минимальное число шагов, необходимое для достижения финиша, в случае невозможности вывести –1.
