Gao the grid III
Time Limit: 2 Seconds
Memory Limit: 65536 KB
Special Judge
A n * m grid as follow:
The height of the grid point at the i^{th} row and j^{th} column is h_{i j}.
The whole grid is under a uniform gravity field.(Gravitational acceleration g = 10m/s^{2}).
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).
Input
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.
Output
For each case, output the expectation time.
A relative or absolute error less than 1e-4 will be accepted.
Sample Input
1 1
1
1 2
2 1
Sample Output
0.000000000
0.632455532
Author:
WU, Yingxin
Source:
ZOJ Monthly, March 2014
Submit
Status