[Swerc2008]First Knight

内存限制：128 MiB 时间限制：1 Sec

提交提交记录讨论

一个m×n的棋盘，左上至右下编号为(1, 1)至 (m, n)，并给定每个格子到周围四个格子的概率　　。

一个骑士从(1, 1)开始，按照给定概率走，问到达(m, n)的期望步数。

题目保证从任一格开始到(m, n)的概率均为1 。

样例输入


			2 2

0.01 0.50

0.00 0.00

0.99 0.00

0.50 0.00

0.00 0.00

0.50 0.00

0.00 0.50

0.00 0.00

1 5

0.0 0.0 0.0 0.0 0.0

1.0 0.1 0.7 0.5 0.0

0.0 0.0 0.0 0.0 0.0

0.0 0.9 0.3 0.5 0.0

3 3

0.000001 0.0 1.0

0.0 1.0 1.0

0.0 0.0 0.0

0.999999 1.0 0.0

1.0 0.0 0.0

0.000001 0.000001 0.0

0.0 0.0 0.0

0.0 0.0 0.0

0.999999 0.0 0.0

0.0 0.0 0.0

0.0 0.0 0.0

0.0 0.999999 0.0

0 0

样例输出


			4.0

41.142857142857146

7.999994000002