[Swerc2008]First Knight

时间限制：1s 空间限制：128MB

题目描述

一个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

提示

没有写明提示

题目来源

WCMG提供SPJ