Лимит времени 1с.
Красная Шапочка спешит навестить свою больную бабушку и отнести ей лекарства и еду. Ее путь лежит через густой лес, который разбит на квадраты. С квадрата в квадрат можно попасть только двигаясь вверх, вниз, влево или вправо. За пределы леса выходить нельзя, лес окружен непроходимым болотом. Лес имеет форму прямоугольника в котором N строк и M столбцов. Красная Шапочка живет в левом верхнем углу этого леса, а ее бабушка — в правом нижнем. Дом бабушки охраняют охотники. Тем лесом бродит Серый Волк, которого очень надо остерегаться Красной Шапочке. К счастью, исходное положение и маршрут его ей известны.
За какую наименьшее количество шагов Красная Шапочка может достичь своей цели, соблюдая при движении такие правила (шаг — это перемещение из клетки в соседнюю клетку):
1. Двигаться можно только в соседнюю по горизонтали или вертикали свободную клетку.
2. Перемещение осуществляется поочередно: сначала Серый Волк, потом Красная Шапочка.
3. Не допускается нахождение в одном квадрате Красной шапочки и Серого Волка.
4. Ходы Красной шапочки и Серого Волка обязательны.
5. Если ходы Серого Волка закончились, то он остается в последней достигнутой клетке. Но заранее известно, что он при этом не заблокирует путь Красной Шапочки к бабушке. Если Серый Волк достиг финиша (квадрата в котором живет бабушка), то его убивают охотники.
Входные данные
В первой строке размер поля: два числа через пробел 0<N, M≤150. Далее идет N строк в каждой из которых по M символов, описывающих поле: точка (.) — Клетка свободна. Решетка (#) — непроходимая клетка. В следующей строке два числа — номер строки и столбца, где изначально находится Серый Волк. Далее идет строка с описанием пути Серого Волка: R — движение вправо, L — влево, U — вверх, D — вниз. Количество ходов соперника не более 32000.
Исходные данные
Единственное число — минимальное число шагов, необходимое для достижения финиша.

3 5
.....
.#...
...#.
1 2
RRLDRRD

Ответ: 8

Как мене представляется — тут можно использовать волновой алгоритм (обход в ширину) Правда возникает тревожное ощущение, что условию задачи может соответствовать ситуация: КШ видит, что столкнется с СВ, отступает на несколько шагов, пропуская волка, а потом двигается дальше. Действительно ли КШ может быть такой интеллектуальной в этой задаче? Если да, то в чем состоит модификация волнового алгоритма? Или тут нужен совсем другой подход? Выполнение программы — 1с.