有一个人被困在一个 R*C(2<=R,C<=1000) 的迷宫中，起初他在 (1,1) 这个点，迷宫的出口是 (R,C)。在迷宫的每一个格子中，他能花费 2 个魔法值开启传送通道。假设他在 (x,y) 这个格子中，开启传送通道之后，有 p_lift[i][j] 的概率被送到 (x,y+1)，有 p_down[i][j] 的概率被送到 (x+1,y)，有 p_loop[i][j] 的概率被送到 (x,y)。问他到出口需要花费的魔法值的期望是多少。
令：f[i][j] 表示从 (i,j) 这个点到出口 (R,C) 花费的魔法值的期望。 那么，我们有：
f[i][j] = p_loop[i][j]*f[i][j] + p_left[i][j]*f[i][j+1] + p_down[i][j]*f[i+1][j]+2
移项可得：
(1-p_loop[i][j])*f[i][j] = p_left[i][j]*f[i][j+1] + p_down[i][j]*f[i+1][j]+ 2（因为这2魔法值是必须要使用的，期望必须加2）
于是我们可以倒着递推了
注意p_loop[i][j]==1的情况，这种情况是永远也走不到r，c的，期望为0。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n,m;
struct aa
{
double r,d,o;
}a[1005][1005];
double f[1005][1005];
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) scanf("%lf%lf%lf",&a[i][j].o,&a[i][j].r,&a[i][j].d);
memset(f,0,sizeof(f));
f[n][m]=0.0;
for (int i=n;i>=1;i--)
for (int j=m;j>=1;j--) if (!(i==n&&j==m))
{
if (a[i][j].o==1.0) continue; //;//该点无路可走,期望值肯定为0(dp[i][j]=0)
f[i][j]=(2+a[i][j].d*f[i+1][j]+a[i][j].r*f[i][j+1])/(1-a[i][j].o);
}
printf("%.3lf\n",f[1][1]);
}
return 0;
}