HDU 3853確率dp

テーマの大意
ある人は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]移項可得:
        (1-p_loop[i][j])*f[i][j] = p_left[i][j](f[i][j+1] + p_down[i][j]*f[i+1][j]

const  int maxn = 1008 ;
double  dp[maxn][maxn]  ;
double  p[maxn][maxn][4]  ;
const double eps = 1e-7 ;

int  main(){
     int i , j , n  , m , u , v ;
     while(cin>>n>>m){
         for(i = 1 ; i <= n ; i++){
             for(j = 1 ; j <= m ; j++){
                  scanf("%lf%lf%lf" ,&p[i][j][1] ,&p[i][j][2] ,&p[i][j][3]) ;
             }
         }
         memset(dp , 0 , sizeof(dp)) ;
         for(i = n ; i >= 1 ; i--){
             for(j = m ; j >= 1 ; j--){
                  if(i == n && j == m) continue ;
                  if(fabs(1.0 - p[i][j][1]) <  eps) continue ;
                  dp[i][j] = (2.0 + p[i][j][2] * dp[i][j+1]+ p[i][j][3] * dp[i+1][j])
                             / (1.0 - p[i][j][1]) ;
             }
         }
         printf("%.3lf
" , dp[1][1]) ;
     }
     return 0 ;
}