Magic Girl’s Teleportation Maze

You are given an n × m grid. Each cell is either black or white. The top‐left cell (1,1) and the bottom‐right cell (n,m) are guaranteed to be black. A magical girl starts at (1,1) and wishes to reach (n,m) while minimizing the expected number of moves.

She can move one step in one of the four cardinal directions (up, down, left, right) without leaving the grid. The rules are as follows:

• If she moves into a black cell, nothing special happens.
• If she moves into a white cell, immediately after the move she is teleported, independently and uniformly at random, to one of the white cells (this may be the same cell) and then continues moving.

Once she reaches cell (n,m) the process stops. Note that upon entering a white cell she loses control of exactly which white cell she gets to continue from. The magical girl can choose her direction at each move so as to minimize the total expected number of moves. Compute this minimum expected number of moves.

Important: Teleportation is instantaneous (does not count as an extra move) but its randomness affects the strategy. In particular, whenever she steps on a white cell the cost incurred is 1 + T where T is the expected cost starting from a uniformly random white cell. Moreover, when moving from any cell (black or white) the available decisions are:

If the adjacent cell is black: the cost is 1 + f(neighbor).

If the adjacent cell is white: the cost is 1 + T (since after stepping into a white cell, teleportation resets her position to a uniformly random white cell and she then proceeds optimally).

Thus, for any cell the recurrence is:

f(x) = min_neighbor ( 1 + [if neighbor is black then f(neighbor) else T] )

Let W be the set of white cells. For any white cell w, denote its value as f(w). Since the teleportation sends the magical girl to a uniformly random white cell, we have:

T = \( \frac{1}{|W|} \sum_{w \in W} f(w) \)

Your task is to compute the minimal expected number of moves from (1,1) to (n,m). If there exists a path composed entirely of black cells, then f(x) on black cells can be computed by simple BFS; otherwise the magical girl must rely on teleportation. In the end, the answer is:

answer = min( f(1,1) via black-only moves, 1 + T )

It is guaranteed that (1,1) and (n,m) are black.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 1000) denoting the dimensions of the grid.

Each of the next n lines contains a string of length m consisting only of the characters B and W, representing black and white cells respectively. It is guaranteed that the top‐left cell (1,1) and bottom‐right cell (n,m) are both black.

outputFormat

Output a single number – the minimum expected number of moves required to reach (n,m) from (1,1). Answers within an absolute or relative error of 1e-6 will be considered correct.

sample

2 2
BB
BB

2.0000000000