Random Walk

Program time limit: 1 second

Program memory limit: 512 MB

The corgi is lost in the matrix maze again! The corgi's mom needs to know when to expect the corgi to come home in order to cook dinner.

Within the matrix, there will be walls, and empty spaces. The corgi is currently at position $(0, 0)$, and home is at position $(n, m)$. The corgi really doesn't know the way, so at each step, the corgi will walk in a random direction (provided that it doesn't walk off the matrix or hit a wall). Can you please help corgi mom to deteremine the expected number of steps the corgi will take to reach home.

It is guaranteed that there exists a path from $(0, 0)$ to $(n, m)$

Input

The first line will contain two space seperated integers $n$ $m$ indicating that it is an $n \times m$ matrix.

The next $n$ lines will each have $m$ characters, represeting the matrix. Each character is either a . representing empty space, or a # representing a wall.

Constraints

For all test cases:

• $1 \le n, m \le 10$.

Output

Output a single float, rounded to 4 decimal point, indicating the expected number of steps the corgi needs to take to reach home.

Sample Input 1

2 2
.#
..

Sample Output 1

4.0000

Explanation 1

Consider all the possible cases that can happen, there is a $\frac{1}{2}$ chance that the corgi can will back in 2 steps, a $\frac{1}{4}$ chance it will walk back in 4 steps...

Thus the answer is $\frac{1}{2} \times 2 + \frac{1}{4} \times 4 + \frac{1}{8} * 6 \dots$

This is an infinite sum that converges to 4, thus the solution is 4.

Note

It can be proven that when generated correctly, the sum of the infinte series that calculates the expected value would always converge.

Scoring

Your program will be run on the 1 sample case and multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves the task. Recall that your final score on the task is the score of your highest scoring submission.

Submit

Past submissions

You haven't submitted to this task.