【题意】一个人要从迷宫的左上角，走到迷宫的右下角。迷宫大小为N*M,在迷宫的某个位置，存在3种可能，一是p1的概率不动，2是p2的概率走到(i+1,j)，3是p3的概率走到(i,j+1)。问从左上角走到右下角的期望步数。


【分析&解题思路】又是一个求期望的套路题，dp[i][j]代表(i,j)到达（R,C）需要消耗的能量，则：dp[i][j]=p1[i][j]*dp[i][j]+p2[i][j]*dp[i][j+1]+p3[i+1][j]*dp[i+1][j]+2;

化简可以得到：dp[i][j]=p2[i][j]*dp[i][j+1]/(1-p1[i][j])+p3[i][j]*dp[i+1][j]/(1-p1[i][j])+2/(1-p1[i][j]);这题还有个坑，就是p[i][j]==1的时候，题目答案保证小于10000000.但有的点是可以不用到达的，所以这样的点出现p1[i][j]==1是允许的。


【AC代码】

//Cloud , you are my sunshine!
//I can't live without you!
//You are the most beautiful girl in the world!
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define eps 1e-10
const int maxn = 1002;
double dp[maxn][maxn];
double p1[maxn][maxn],p2[maxn][maxn],p3[maxn][maxn];
int main(){
    int R,C;
    while(~scanf("%d%d",&R,&C)){
        for(int i=1; i<=R; i++)
            for(int j=1; j<=C; j++)
                scanf("%lf%lf%lf",&p1[i][j],&p2[i][j],&p3[i][j]);
        dp[R][C]=0;
        for(int i=R; i>=1; i--){
            for(int j=C; j>=1; j--){
                if(i==R&&j==C) continue;
                if(fabs(1-p1[i][j])<eps) continue;//注意这里
                dp[i][j]=p2[i][j]/(1-p1[i][j])*dp[i][j+1]+p3[i][j]/(1-p1[i][j])*dp[i+1][j]
                +2.0/(1-p1[i][j]);
            }
        }
        printf("%.3f\n",dp[1][1]);
    }
    return 0;
}