题解 | #蘑菇阵#

简单的动态规划问题：

1. 确定dp数组的含义：dp[i][j] 表示到达[i, j] 位置的概率
2. 初始化：对于第一行和第一列要做特别的初始化处理。因为在边界只有一种选择
3. 状态转移方程：
4. 确定递推方向：从上到下，从左往右

#include <iostream>
#include <vector>
using namespace std;

double A2B(vector<vector<double>>& dp) {
   	// dp数组的初始化
    dp[0][0] = 1; 
    int n = dp.size(), m = dp[0].size();
    for (int i = 1; i < n; i++) {
        if (dp[i][0] == -1) dp[i][0] = 0;
        else dp[i][0] = dp[i - 1][0] / 2;
    }

    for (int j = 1; j < m; j++) {
        if (dp[0][j] == -1) dp[0][j] = 0;
        else dp[0][j] = dp[0][j - 1] / 2;
    }
	// 状态转移方程
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (dp[i][j] == -1) dp[i][j] = 0;
            else {
                dp[i][j] += i == n - 1 ? dp[i][j - 1] : dp[i][j - 1] / 2;
                dp[i][j] += j == m - 1 ? dp[i - 1][j] : dp[i - 1][j] / 2;
            }
        }
    }
    return dp[n - 1][m - 1];
}

int main() {
    int n, m, k;
    while (cin >> n >> m) {
        cin >> k;
        vector<vector<double>> dp(n, vector<double>(m, 0));
        for (int i = 0; i < k; i++) {
            int x, y;
            cin >> x >> y;
            dp[x - 1][y - 1] = -1.0;  // -1 表示有蘑菇
        }
	  // 可以排除只有一行或者一列，但没有蘑菇的特殊情况
        if(k == 0) cout << "1.00" << endl; 
        else {
            double ans = A2B(dp);
            printf("%.2lf\n", ans);
        }
    }
}