Задача №1378. Правила дорожного движения

Город, в котором живет Петя имеет вид прямоугольника, улицы в нем образуют сетку MxN. Перед каждым перекрестком на подъезде к нему может стоять дорожный знак. Также знак может стоять после перекрестка у въезда на улицу.

В городе встречаются следующие виды дорожных знаков: знаки, установленные перед перекрестком – поворот только направо (R), поворот только налево (L), только проезд прямо (F), поворот налево запрещен (NL), поворот направо запрещен (NR), проезд прямо запрещен (NF); знаки, установленные после перекрестка – проезд запрещен (S), максимальная скорость до ближайшего перекрестка – X км/ч. (!X). В отсутствие ограничивающего знака максимальная скорость равна Y км/ч. Длина всех улиц одинакова и равна L метров. Разворачиваться на перекрестке и ехать в строго противоположном направлении не разрешается.

Петя живет в доме около перекрестка, где пересекаются xs-я вертикальная и ys-я горизонтальная улицы (улицы нумеруются, начиная с 1). Петин папа работает на заводе около перекрестка, где пересекаются xd-я вертикальная и yd-я горизонтальная улицы. Помогите Пете выяснить, какое минимальное время требуется папе, чтобы доехать на работу, если Петин папа – законопослушный водитель и соблюдает все правила дорожного движения.

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

Первая строка входного файла содержит целые числа M, N (1 M, N 20), Y (1 Y 80), L (1  L  10000), xs, ys, xd и yd (1 xs, xd N, 1 ys, yd M, (xs, ys) (xd, yd)).

Следующие MN строк содержат информацию о знаках, расположенных на соответствующих перекрестках (порядок перечисления перекрестков следующий: сначала идут перекрестки, расположенные на 1-й горизонтальной улице, в возрастающем порядке номеров вертикальных улиц, затем перекрестки, расположенные на 2-й горизонтальной улице, и т.д.)

Формат информации о знаках следующий: описания знаков разделяются запятыми, сначала идет буква латинского алфавита, означающая направление, в котором уходит с перекрестка улица, на которой стоит знак, затем после двоеточия идет обозначение знака (направления обозначаются буквами N, S, E и W – см. рисунок). После последнего знака идет точка. По типу знака понятно, находится он до или после перекрестка. Ограничение скорости – целое число, 1 X 80.

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

Выведите в выходной файл единственное число – округленное до ближайшего целого минимальное количество секунд, необходимое Петиному папе, чтобы добраться до работы (допускается ошибка в 1 секунду).

Примеры
Входные данные
3 4 60 5000 2 2 4 3
.
.
S:NL.
.
E:L.
N:S,E:S,S:S,W:!25.
S:NR.
.
.
E:!72,N:!80,W:!15.
E:!10.
.
Выходные данные
3070
Сдать: для сдачи задач необходимо войти в систему