Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3766
Gao the grid III

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

A n * m grid as follow:

a n*m grid(n=4,m=3)

The height of the grid point at the ith row and jth column is hi j.
The whole grid is under a uniform gravity field.(Gravitational acceleration g = 10m/s2).
In the beginning, there is a little ball at point(0, 0) with 0 kinetic energy. It can move along the grid lines to adjacent grid points.
The motion of the ball obeys the law of the conservation of energy. But the direction of motion allows sudden change.
When the ball moves along a direction and arrives in point(p, q), it randomly choose a direction with equal probability among all feasible directions(It depends on whether the energy is enough).
Please calculate the expectation time it takes to move from point(0, 0) to point(n - 1, m - 1).
Output "Never reach!" if the ball can never move to point(n - 1, m - 1).


The input consists of several cases. The first line of each case consists of two positive integers n and m (1 ≤ n, m ≤ 8), indicating the size of the grid. The following n lines each with m non-negative integers(≤ 100000) describe the height of each grid point. Adjacent heights are different.


For each case, output the expectation time. A relative or absolute error less than 1e-4 will be accepted.

Sample Input

1 1
1 2
2 1

Sample Output


Author: WU, Yingxin
Source: ZOJ Monthly, March 2014
Submit    Status