题目大意
有一个人被困在一个 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) 这个点到下一点花费的魔法值的期望。
那么，我们有：
f[i][j] = 2+p_loop[i][j]*f[i][j] + p_left[i][j]*f[i][j+1] + p_down[i][j]*f[i+1][j]
移项可得：
(1-p_loop[i][j])*f[i][j] = 2+p_left[i][j](f[i][j+1] + p_down[i][j]*f[i+1][j]
#include<stdio.h>
#include<math.h>
#include<string.h>
double p[][][];
double f[][];
bool vs[][];
int R,C;
double DP(int x,int y)
{
if(x==R&&y==C)return ;
if(x>R||y>C)return ;
if(vs[x][y])return f[x][y];
if(fabs(p[][x][y]-)<1e-)
{
vs[x][y]=;
return f[x][y]=;
}
vs[x][y]=;
return f[x][y]=(+p[][x][y]*DP(x,y+)+p[][x][y]*DP(x+,y))/(-p[][x][y]);
}
int main()
{
while(scanf("%d%d",&R,&C)!=EOF)
{
for(int i=;i<=R;i++)
for(int j=;j<=C;j++)
scanf("%lf%lf%lf",&p[][i][j],&p[][i][j],&p[][i][j]);
memset(f,,sizeof(f));
memset(vs,,sizeof(vs));
printf("%.3lf\n",DP(,));
}
}