【HDU3853】LOOPS

题目链接：传送门
题解：
很容易想到用 <nobr> dp[i][j] </nobr>表示从 <nobr> (i,j) </nobr>走到 <nobr> (r,c) </nobr>的期望，那么有
<nobr> dp[i][j]=p[i][j][1]×dp[i][j]+p[i][j][2]×dp[i][j+1]+p[i][j][3]×dp[i+1][j]+2 </nobr>
然后整理一下得到
<nobr> dp[i][j]=p[i][j][2]×dp[i][j+1]+p[i][j][3]×dp[i+1][j]+21−p[i][j][1] </nobr>
注意特判一下原地不动的概率为1的情况（此时分母为零）

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

const int N=1005;
double f[N][N],p[N][N][3];
int r,c;

int main()
{
    while(~scanf("%d%d",&r,&c))
    {
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                for(int k=0;k<=2;k++)
                    scanf("%lf",&p[i][j][k]);
        f[r][c]=0; 
        for(int i=r;i;i--)
            for(int j=c;j;j--)
            {
                if(p[i][j][0]==1||(i==r&&j==c)) continue;
                f[i][j]=(f[i][j+1]*p[i][j][1]+f[i+1][j]*p[i][j][2]+2)/(1-p[i][j][0]);
            }
        printf("%.3f\n",f[1][1]);
    }
    return 0;
}