HDU 3853 LOOPS：期望 DP 解迷宮逃脫期望步數

題目大意

R×C 網格 (R,C ≤ 1000)，起點 (1,1)，終點 (R,C)。每格有傳送門：概率 p1 傳送到右格，p2 到下格，p3 原地停留。每次傳送消耗 2 魔力。求從起點到終點的期望魔力消耗。保證 p1+p2+p3=1，邊界概率為 0。

期望 DP 方程

設 E[i][j] 為從 (i,j) 到終點的期望代價。
終點：E[R][C] = 0。
一般格子：
E = p1*(E[i][j+1]+2) + p2*(E[i+1][j]+2) + p3*(E[i][j]+2)
移項：(1-p3)*E = p1*E[i][j+1] + p2*E[i+1][j] + 2
∴ E[i][j] = (p1*E[i][j+1] + p2*E[i+1][j] + 2) / (1 - p3)。

計算順序：逆序 DP

依賴右、下兩格，故從右下向左上逆序計算：i = R..1, j = C..1。邊界處 p1 或 p2 為 0，公式自動退化。

C++ 代碼

#include 
using namespace std;
const int MAXN = 1005;
double p1[MAXN][MAXN], p2[MAXN][MAXN], p3[MAXN][MAXN];
double dp[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int R, C;
    while (cin >> R >> C) {
        for (int i = 1; i <= R; ++i)
            for (int j = 1; j <= C; ++j)
                cin >> p1[i][j] >> p2[i][j] >> p3[i][j];
        dp[R][C] = 0;
        for (int i = R; i >= 1; --i) {
            for (int j = C; j >= 1; --j) {
                if (i == R && j == C) continue;
                if (fabs(1 - p1[i][j]) < 1e-8) continue; // p1≈1 會導致分母為0，但題目保證不會
                dp[i][j] = (p2[i][j]*dp[i][j+1] + p3[i][j]*dp[i+1][j] + 2) / (1 - p1[i][j]);
            }
        }
        cout << fixed << setprecision(3) << dp[1][1] << '\n';
    }
    return 0;
}

注意點

• 分母 1 - p1 不為 0（題目保證 p1 < 1，否則無解）。
• 輸出保留 3 位小數 fixed << setprecision(3)。
• 多測試用例直到 EOF。

總結

HDU 3853 是「期望 DP 逆序計算」的標準題。核心步驟：列出期望方程 → 移項解出 E[i][j] → 確定拓撲序（逆序） → 邊界處理。同模板解決 POJ 3009、Codeforces 期望步數問題。