题解 | 蘑菇阵

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

int main() {
    int n, m, k;
    while(cin >> n >> m >> k){
        vector<vector<int>> st(n + 2, vector<int>(m + 2));
        vector<vector<double>> dp(n + 2, vector<double>(m + 2));
        while(k --){
            int x, y;
            cin >> x >> y;
            st[x][y] = 1;
        }
        for(int i = 1 ; i <= n ; i ++){
            st[i][m + 1] = 1;
        }
        for(int i = 1 ; i <= m ; i ++){
            st[n + 1][i] = 1;
        }
        dp[1][1] = 1;
        for(int i = 1 ; i <= n ; i ++){
            for(int j = 1 ; j <= m ; j ++){
                if(st[i][j]){
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j + 1] += dp[i][j] / (i + 1 > n ? 1 : 2);
                dp[i + 1][j] += dp[i][j] / (j + 1 > m ? 1 : 2); 
                
            }
        }
        printf("%.2lf\n", dp[n][m]);
    }
}
// 64 位输出请用 printf("%lld")