1 /* 2 题目大意：一个n*c的网格，求从(1,1)到(n,c)花费魔法值的期望。 3 每次开启一个通道需要花费2魔法值，有三个方向可以走 4 在(x,y)位置时,分别转向 5 1.(x,y),概率是p(x,y*3-2) 6 2.(x,y+1),概率是p(x,y*3-1) 7 3.(x+1,y),概率是p(x,y*3) 8  9 dp[x][y]=p[x][y*3-2]*d[x][y]+p[x][y*3-1]*dp[x][y+1]+p[x][y*3]*dp[x+1][y]+2;10 */11 #include <iostream>12 #include <cstdio>13 #include <cstring>14 #include <cmath>15 using namespace std;16 17 const double eps=1e-8;18 const int maxn=1005;19 double p[maxn][3*maxn],dp[maxn][maxn];20 21 int main()22 {23     int n,m,i,j;24     while(~scanf("%d%d",&n,&m))25     {26         memset(p,0,sizeof(p));27         memset(dp,0,sizeof(dp));28         for(i=1;i<=n;i++)29         {30             for(j=1;j<=3*m;j++)31                 scanf("%lf",&p[i][j]);32         }33         for(i=n;i>0;i--)34         {35             for(j=m;j>0;j--)36             {37                 if(i==n && j==m) continue;38                 if(fabs(1-p[i][j*3-2])<eps) //呆在原地的概率为139                     continue;40                 dp[i][j]=(p[i][j*3-1]*dp[i][j+1]+p[i][j*3]*dp[i+1][j]+2)/(1-p[i][j*3-2]);41             }42         }43         printf("%.3lf\n",dp[1][1]);44     }45     return 0;46 }