Problem C
Gruesome Cave

It is pitch black. You are likely to be eaten by a grue.

The archaeologist Joanina Iones has been hard at work deciphering the arcane glyphs in front of a secret cave entrance. The glyphs tell the story of the cave: It has existed long before the beginning of time, and with it, a single grue was brought to life. It has, of course, also a diamond in it, which is why Joanina is here.

Encountering a grue will always lead to a horrible death, but fortunately Joanina knows how grues work:

• Every hour, a grue moves to a random neighboring tile with uniform probability, except if a human is in the cave. While a human is in the cave it stays in one place.

• A grue does not like diamonds nor cave entrances, so it will never move to a cave entrance or a diamond tile.

The glyphs also describe the map of the cave, as well as where the diamond is located. If Joanina wants to retrieve the diamond, how likely is it she encounters the grue using the least risky path?

Input

The first line of the input consists of two space-separated integers $L$ and $W$, indicating the length and width of the map, respectively.
Then follows $L$ lines each consisting of a string of length $W$. Here, ‘ ’ denotes an empty tile, ‘#’ denotes a wall, ‘E’ denotes the cave entrance and ‘D’ denotes the diamond’s location.

Output

Output the probability that Joanina will encounter the grue, assuming she chooses the least risky path. Your answer must have an absolute or relative error of at most $10^{-6}$.

Limits

• $3 \leq L, W \leq 30$

• $2 \leq S \leq 70$, where $S$ is the number of ‘ ’ tiles.

• The border of the map can only contain ‘E’ and ‘#’ tiles.

• The map will only contain the characters ‘ ’, ’#’, ’E’ and ’D’ and there will only be one ’E’ character and one ’D’ character per map.

• There will always be a way from the entrance to the diamond.

• All ‘ ’ tiles form a connected graph.

5 6
######
## ###
E   D#
## ###
######

0.75