Problem1450--PIPI上学路II

1450: PIPI上学路II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 84  Solved: 47
[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

Source/Category

中等 动态规划 
[Submit] [Status]