HDU 3853

考虑到有留在原地概率为1的情况，好吧，我直接把它置0.然后，真的过了。

还是使用逆推。。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 1005
using namespace std;

double qi[N][N];
double p[N][N][3];
int main(){
	int r,c;
	while(scanf("%d%d",&r,&c)!=EOF){
		for(int i=1;i<=r;i++){
			for(int j=1;j<=c;j++){
				scanf("%lf%lf%lf",&p[i][j][0],&p[i][j][1],&p[i][j][2]);
			}
		}
		qi[r][c]=0;
		for(int i=r;i>=1;i--){
			for(int j=c;j>=1;j--){
				if(i==r&&j==c)
				continue;
				if(p[i][j][0]==1.0)
				qi[i][j]=0;
				else{
					qi[i][j]=(qi[i][j+1]*p[i][j][1]+qi[i+1][j]*p[i][j][2]+2)/(1-p[i][j][0]);
				}
			}
		}
		printf("%.3lf
",qi[1][1]);
	}
	return 0;
}