Hdu 3853(概率期望DP)

hdu 3853
设$dp(i,j)$为$(i,j)$到$(r,c)$的步数期望，那么可以列出下列状态转移方程：
$$dp(i,j)=\frac{dp(i,j+1) \times P_2 + dp(i+1,j) \times P_3}{1-P_1}$$
但是当$P_1=1$时，$dp(i,j)=0$，因为这个点肯定无法到达终点，设为$0$表示该点不影响其他点。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000 + 5, P1 = 0, P2 = 1, P3 = 2;
const db eps = 1e-9; 
db p[MAXN][MAXN][3], dp[MAXN][MAXN];
int r, c;
void clean() {
    ms(dp, 0);
}
void solve() {
    clean();
    for (int i=1;i<=r;i++) {
        for (int j=1;j<=c;j++) {
            scanf("%lf%lf%lf", &p[i][j][P1], &p[i][j][P2], &p[i][j][P3]);
        }
    }
    for (int i=r;i>=1;i--) {
        for (int j=c;j>=1;j--) {
            if (fabs(1.0-p[i][j][P1])<eps) continue;
            dp[i][j] = (db)(dp[i][j+1]*p[i][j][P2]+dp[i+1][j]*p[i][j][P3]+2)/(db)(1.0-p[i][j][P1]);
        }
    }
    printf("%.3f\n", dp[1][1]);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d%d", &r, &c)==2) solve();
    return 0;
}