题意：在一个R*C的迷宫里，一个人在最左上角，出口在右下角，在每个格子上，该人有几率向下，向右或者不动，求到出口的期望 现在对概率dp有了更清楚的认识了 设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][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]);
注意一种情况就是p1[i][j]==1的情况。
题目只是保证答案小于1000000.但是有的点可能永远都不可能到达的。
所以这样的点出现p1[i][j]是允许的。
否则就会WA了。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const int INF=0x3f3f3f3f;
const double eps=1e-;
typedef long long ll;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int n,m,tt;
double p1[MAXN][MAXN],p2[MAXN][MAXN],p3[MAXN][MAXN],dp[MAXN][MAXN];
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=;i<n;i++)
{
for(j=;j<m;j++)
{
scanf("%lf%lf%lf",&p1[i][j],&p2[i][j],&p3[i][j]);
}
}
cl(dp);
for(i=n-;i>=;i--)
{
for(j=m-;j>=;j--)
{
if(i==n-&&j==m-) continue;
if(fabs(p1[i][j]-)<eps)
{
dp[i][j]=;
continue;
}
dp[i][j]=p2[i][j]*dp[i][j+]/(-p1[i][j])+p3[i][j]*dp[i+][j]/(-p1[i][j])+/(-p1[i][j]);
}
}
printf("%.3f\n",dp[][]);
}
}