Batman Begins

Ra's Al Ghul heads the centuries-old League of Shadows and is an international terrorist. What he wants is a world in perfect environmental balance, and he believes the best way to reach that balance is to wipe out most of humanity.

As corruption spread through Gotham City, Ra's Al Ghul decided to destroy the city with a biological weapon. He plans to move a powerful microwave emitter to the main water hub of Gotham City by train and release a genetically engineered virus there. Batman and James Gordon decided to stop him, and Gordon drives the Batmobile to reach the water hub before the train does. Write a program that computes the minimum time Gordon needs to get there.

Gotham City is a grid of intersections. $H$ roads run east to west, $V$ roads run north to south, and two intersections next to each other on the same road are $D$ metres apart. Some intersections are closed, so the Batmobile can neither enter nor drive through them. Water surrounds the city on every side, so the Batmobile cannot leave the grid either.

The Batmobile works like this.

1. It starts at rest at Gordon's intersection.
2. Its acceleration and its deceleration always have magnitude $a$ m/s$^2$.
3. It has a top speed, and it reaches that speed from rest in 5 seconds. The top speed is therefore $5a$ m/s, and the Batmobile never drives faster.
4. It drives along the roads only, and it has to come to a full stop before it turns left or right.
5. It has to arrive at the water hub at speed zero.

Driving straight through an open intersection keeps the current speed. Every grid holds exactly one starting intersection and exactly one water hub, and the water hub is always reachable.

The equations of linear motion with constant acceleration are

$v_f = v_i + a t$

$v_f^2 = v_i^2 + 2 a (x_f - x_i)$

$x_f = x_i + v_i t + \frac{1}{2} a t^2$

The first line holds the number of test cases $T$ ($1 \le T \le 100$).

The first line of each test case holds four integers $H$, $V$, $D$ and $a$ ($1 \le H, V \le 500$, $1 \le D \le 1000$, $1 \le a \le 1000$): the number of horizontal roads, the number of vertical roads, the distance in metres between two adjacent intersections, and the acceleration of the Batmobile in m/s$^2$.

The next $H$ lines hold $V$ characters each. # is a closed intersection, G is Gordon's starting intersection, W is the water hub, and . is an open intersection.

For each test case, print the minimum time in seconds needed to reach the water hub on its own line. Round the value at the third decimal place and print two decimals, rounding a value exactly halfway up. Keep a trailing zero in the second decimal place.

The answer is always further than $10^{-6}$ from a rounding boundary, so double precision arithmetic is enough.