401794: GYM100528 K Парковка

K. Парковкаограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводstandard inputвыводstandard output

Вася сделал покупки в популярном торговом центре и теперь хочет отправиться домой. Для этого ему сначала нужно выехать на своей машине с парковки. Задача эта не очень простая, поскольку на парковке находится множество машин других посетителей торгового комплекса. Сама же парковка представляет собой прямоугольную область N × M клеток. В одной из клеток находится машина Васи. В других клетках могут находиться машины остальных покупателей. Кроме того, в некоторых клетках (по крайней мере, в одной) находятся выезды с парковки.

Вася хочет доехать до одного из выездов с парковки. Вася может перемещаться на машине из текущей клетки в соседнюю по стороне клетки, если эта клетка находится на парковке и свободна от других машин. В процессе переезда Вася может увеличивать скорость автомобиля максимум на A или уменьшать скорость автомобиля максимум на B. Итого, если до переезда скорость автомобиля была равна V, то после переезда на новую клетку скорость может быть любым (не обязательно целым) числом в интервале [V - B, V + A] по желанию Васи, с единственным ограничением — скорость не может быть ниже 1. Если в начале переезда скорость машины была равна V₁, а после — стала равна V₂, то будем считать, что Вася потратил 2 / (V₁ + V₂) времени на переезд. Кроме того, Вася может менять направление движения, только если скорость автомобиля равна 1. Это значит, что если Вася уже совершил переезд из одной клетки в другую и его скорость после переезда больше 1, то он может продолжать двигаться только в том же направлении. Если же следующая клетка в этом направлении занята машиной или находится за пределами парковки, то такое движение запрещено. Однако приезжать к выезду с парковки можно на любой скорости (даже если следующая клетка в направлении движения занята).

Определите, за какое наименьшее время Вася сможет добраться до какого-либо из выездов с парковки. Покидать парковку, выходя за пределы исходной области N × M, запрещено. Машины других покупателей не двигаются. Начальная скорость машины Васи равна 1.

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

В первой строке входного файла находятся 4 целых числа — размеры парковки N и M (1 ≤ N, M ≤ 200), а так же числа A и B (1 ≤ A, B ≤ 100). Следующие N строк описывают начальное состояние парковки. Каждая строка имеет длину M и состоит из символов '.', 'C', 'V', 'E'. Символ '.' соответствует пустой клетке парковки, 'C' — занятой автомобилем, 'V' — клетка, в которой находится машина Васи, 'E' — клетки, представляющие собой выезды с парковки. Гарантируется, что присутствует ровно один символ 'V', не менее одного символа 'E' и что Вася может добраться хотя бы до одного выезда с парковки.

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

Вывести единственное вещественное число с абсолютной или относительной погрешностью, не превышающей 10^- 6 — минимальное время, за которое Вася сможет добраться до одного из выездов с парковки.

ПримерыВходные данные

2 2 2 2
VE
..

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

0.500000000

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

2 3 1 1
V..
..E

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

2.000000000

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

2 3 1 1
VC.
..E

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

2.066666667

Примечание

В первом примере Вася при переезде с клетки (1, 1) в клетку (1, 2), содержащую выезд с парковки, может увеличить скорость с 1 до 3. При этом он потратит время, равное 2 / (1 + 3) = 0.5.

Во втором примере оптимально двигаться из клетки (1, 1) в клетку (1, 2), увеличив скорость до 2. Затем — в клетку (1, 3), снизив скорость до 1 из-за поворота. Далее — в клетку (2, 3), увеличив скорость до 2. Итого, будет потрачено время 2 / (1 + 2) + 2 / (2 + 1) + 2 / (1 + 2) = 2.

В третьем примере нельзя двигаться так же, как в предыдущем, поскольку клетка (1, 2) занята другой машиной. Необходимо двигаться сначала в клетку (2, 1) на скорости 1, затем повернуть на клетку (2, 2), увеличив скорость до 2, далее — в клетку (2, 3), увеличив скорость до 3. Итого, Вася потратит единиц времени.