Problem D: PIPI上学路II

Problem D: PIPI上学路II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 81  Solved: 44
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI每天早上都要从CSU的某个位置走到另一个位置。CSU可以抽象为一个n*m的方格。PIPI每天都要从(1,1)走到(n,m),每次PIPI可以向下/向右移动一格或者不动,概率分别为P1 , P2, P3 (P1+P2+P3=1)。 请求PIPI从(1,1)走到(n,m)所需步数的期望。保证答案一定存在。

Input

输入包含多组测试用例(case≤10)。
对于每组测试用例,第一行输入两个整数 n , m (1<=n,m <=100)。
接下来一共n行,每一行包含3*m个浮点数。第i行第 3*j , 3*j+1, 3*j+2分别代表第i行,第j列格子上的P1, P2 ,P3(0=<Pi<=1 , i=1,2,3,除了位置(n,m),保证P3<1)。

Output

对于每组测试用例,输出PIPI从(1,1)走到(n,m)所需步数的期望,答案保留三位小数。

Sample Input

1 2
0 0.3 0.7 0.0 0.0 1.0
2 2
0.5 0.5 0.0 0.5 0.0 0.5
0.0 0.5 0.5 0.0 0.0 1.0

Sample Output

3.333
3.000