題目如下：

/**
現(xiàn)在有兩個好友A和B，住在一片長有蘑菇的由n＊m個方格組成的草地，A在(1,1),B在(n,m)。
現(xiàn)在A想要拜訪B，由于她只想去B的家，所以每次她只會走(i,j+1)或(i+1,j)這樣的路線，
在草地上有k個蘑菇種在格子里(多個蘑菇可能在同一方格),
問：A如果每一步隨機(jī)選擇的話(若她在邊界上，則只有一種選擇)，
那么她不碰到蘑菇走到B的家的概率是多少？

輸入描述:
第一行N，M，K(1 ≤ N,M ≤ 20, k ≤ 100),N,M為草地大小，接下來K行，
每行兩個整數(shù)x，y，代表(x,y)處有一個蘑菇。

輸出描述:
輸出一行，代表所求概率(保留到2位小數(shù))

輸入例子1:
2 2 1
2 1

輸出例子1:
0.50
*/

思路如下：

題目要求在當(dāng)前方格只能往右邊、下邊這任意選擇兩個方向到達(dá)下一個方格
若當(dāng)前方格被阻擋，那么其能到達(dá)概率為0
base case:(針對沒有被阻擋情況，若有阻擋直接置為0即可)
dp[0][j]=dp[i][0]=1
i==m-1 || j==n-1
情況其左邊(i, j-1)->(i,j)只有一種選擇，權(quán)重為1
j==n-1同理
其余情況
其左邊(i, j-1)->(i,j)有兩種選擇權(quán)值為0.5
具體更新過程看代碼

代碼如下：

#include<stdio.h>
#include<iostream>

#define MAX_M 25
#define MAX_N 25

using namespace std;

bool blockMap[MAX_M][MAX_N];
double dp[MAX_M][MAX_N];

int main()
{
    int m, n, k;
    while(scanf("%d%d%d", &m, &n, &k)==3)
    {
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                blockMap[i][j]=false;
                dp[i][j]=0;
            }
        }
        for(int i=0; i<k; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            blockMap[x-1][y-1]=true;
        }
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(blockMap[i][j])
                {
                    dp[i][j]=0;
                    continue;
                }
                if(i==0 && j==0)
                {
                    dp[i][j]=1.0;
                    continue;
                }
                dp[i][j]=0;
                if(i==m-1)
                {
                    dp[i][j]+=dp[i][j-1];
                }
                else
                {
                    dp[i][j]+=(0.5*dp[i][j-1]);
                }
                if(j==n-1)
                {
                    dp[i][j]+=dp[i-1][j];
                }
                else
                {
                    dp[i][j]+=(0.5*dp[i-1][j]);
                }
            }
        }
        printf("%.2lf\n", dp[m-1][n-1]);
    }
    return 0;
}