笔试刷题-百度2018-06-25

题目如下：

/**
现在有两个好友A和B，住在一片长有蘑菇的由n＊m个方格组成的草地，A在(1,1),B在(n,m)。
现在A想要拜访B，由于她只想去B的家，所以每次她只会走(i,j+1)或(i+1,j)这样的路线，
在草地上有k个蘑菇种在格子里(多个蘑菇可能在同一方格),
问：A如果每一步随机选择的话(若她在边界上，则只有一种选择)，
那么她不碰到蘑菇走到B的家的概率是多少？

输入描述:
第一行N，M，K(1 ≤ N,M ≤ 20, k ≤ 100),N,M为草地大小，接下来K行，
每行两个整数x，y，代表(x,y)处有一个蘑菇。

输出描述:
输出一行，代表所求概率(保留到2位小数)

输入例子1:
2 2 1
2 1

输出例子1:
0.50
*/

思路如下：

题目要求在当前方格只能往右边、下边这任意选择两个方向到达下一个方格
若当前方格被阻挡，那么其能到达概率为0
base case:(针对没有被阻挡情况，若有阻挡直接置为0即可)
dp[0][j]=dp[i][0]=1
i==m-1 || j==n-1
情况其左边(i, j-1)->(i,j)只有一种选择，权重为1
j==n-1同理
其余情况
其左边(i, j-1)->(i,j)有两种选择权值为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;
}