C 解法, 执行用时: 2ms, 内存消耗: 224KB, 提交时间: 2018-12-29

#include <stdio.h>
#include <string.h>

int N, M, K;
char mushroom[21][21];
float dp[21][21];

int main(int argc, char *argv[])
{
    int i, j, x, y;
    
    while(scanf("%d%d%d", &N, &M, &K) == 3)
    {
        for(i = 0; i < K; i++)
        {
            scanf("%d%d", &x, &y);
            mushroom[x][y] = 1;
        }
        
        for(i = 1; i <= N; i++)
        {
            for(j = 1; j <= M; j++)
            {
                if(i == 1 && j == 1) 
                {
                    dp[i][j] = 1; 
                }
                else if(mushroom[i][j]) 
                {
                    dp[i][j] = 0; 
                }
                else if(i == N && j == M) 
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; 
                }
                else if(i == N) 
                {
                    dp[i][j] = dp[i - 1][j] * 0.5 + dp[i][j - 1]; 
                }
                else if(j == M) 
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] * 0.5;
                }
                else if(i == 1) 
                {
                    dp[i][j] = dp[i][j - 1] * 0.5; 
                }
                else if(j == 1) 
                {
                    dp[i][j] = dp[i - 1][j] * 0.5; 
                }
                else
                {
                    dp[i][j] = dp[i][j - 1] * 0.5 + dp[i - 1][j] * 0.5;
                }
            }
        }
        printf("%.2f\n", dp[N][M]); 
        
        memset(mushroom, 0, sizeof(mushroom));
    }
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 368KB, 提交时间: 2020-09-03

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(void)
{
    int n, m, k;
    double dp[25][25];    //到达当前格子不碰到蘑菇的概率
    int map[25][25];    //当前格子有无蘑菇
    
    while(scanf("%d%d%d", &n, &m, &k) == 3)
    {
        memset(dp, 0, sizeof(dp));
        memset(map, 0, sizeof(map));
        //double dp[30][30] = {0};    //到达当前格子不碰到蘑菇的概率
        //int map[30][30] = {0};    //当前格子有无蘑菇
        int x, y;
        for(int c = 1; c <= k; c++)
        {
            //int x, y;
            scanf("%d%d", &x, &y);
            map[x][y] = 1;
        }
        
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                if(i == 1 && j == 1)      {dp[i][j] = 1;continue;}
                if(map[i][j])         {dp[i][j] = 0;continue;}
                if(i == n && j == m)      {dp[i][j] = dp[i][j-1] + dp[i-1][j];continue;}
                if(i == n)                {dp[i][j] = dp[i][j-1] + 0.5*dp[i-1][j];continue;}
                if(j == m)                {dp[i][j] = 0.5*dp[i][j-1] + dp[i-1][j];continue;}
                if(i == 1)                {dp[i][j] = 0.5*dp[i][j-1];continue;}
                if(j == 1)                {dp[i][j] = 0.5*dp[i-1][j];continue;}
                
                dp[i][j] = 0.5*dp[i][j-1] + 0.5*dp[i-1][j];
            }
        printf("%.2lf\n", dp[n][m]);
    }
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-06-12

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n,m,k;
    while(cin>>n>>m>>k)
    {
        // 构建map
        vector<vector<int>> map (n+1,vector<int>(m+1)); // 存放 坐标
        // ===============放入蘑菇==============
        int row,col; 
        while(k--)
        {
            cin>> row>>col;
            map[row][col] = 1;
        }
        //状态定义
        vector<vector<double>>dp(n+1, vector<double>(m+1));
        //初始化
        dp[1][1] = 1.0;
        
        // 状态转移
        for(int i =1; i<= n; i++)
        {
            for(int j = 1; j<= m; j++)
            {
                if(!(i ==1 && j == 1))
                {   // 状态转移方程
                    dp[i][j] = dp[i-1][j] * (j == m?1 : 0.5) + dp[i][j-1]*(i==n?1:0.5);
                }
                
                // 如果该位置为蘑菇，则到达该位置的概率为0’
                if(map[i][j])
                {
                    dp[i][j] = 0;
                }
            }
        }
        // 返回结果
        printf("%.2f\n", dp[n][m]);
    }
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-08-16

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

int main() {
    int n, m, k;
    while(cin >> n >> m >> k){
    
    vector<vector<double>> groom(n, vector<double>(m, 0));
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        groom[a - 1][b - 1] = -1;
    }
    groom[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (groom[i][j] == -1) {
                //groom[i][j] = 0;
                continue;
            }
            if (i != n - 1 || j != m - 1) {
                if (i != n - 1 && j != m - 1) {
                    if (groom[i + 1][j] != -1) {
                        groom[i + 1][j] += groom[i][j] * 0.5;
                    }
                    if (groom[i][j + 1] != -1) {
                        groom[i][j + 1] += groom[i][j] * 0.5;
                    }

                }
                else if (j != m - 1) {
                    if (groom[i][j + 1] != -1) {
                        groom[i][j + 1] += groom[i][j];
                    }

                }
                else if (i != n - 1) {
                    if (groom[i + 1][j] != -1) {
                        groom[i + 1][j] += groom[i][j];
                    }

                }
            }
        }
    }
    //printf("%.2f\n", groom[n - 1][m - 1]);
    cout << fixed << setprecision(2) << groom[n - 1][m - 1] << endl;
    }
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 380KB, 提交时间: 2020-12-23

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


int main(){
    int N, M, K;
    while(cin >> N >> M >> K){
        vector<vector<double>> map(N + 1, vector<double>(M + 1, 0));
        map[1][1] = 1;
        
        vector<vector<int>> flag(N + 1, vector<int>(M + 1, 0));
        int x, y;
        for(int i = 0; i < K; i++){
            cin >> x >> y;
            flag[x][y] = 1;
        }
        
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                if(i == 1 && j == 1){
                    continue;
                }
                
                map[i][j] = map[i - 1][j] *(j == M ? 1 : 0.5) +
                    map[i][j - 1] * (i == N ? 1 : 0.5);
                
                if(flag[i][j]){
                    map[i][j] = 0;
                }
            }
        }
        
        
        cout << fixed << setprecision(2) << map[N][M] << endl;
    }
    
    return 0;
}