求助 蘑菇阵 这道题

牛牛题库BD4 蘑菇阵

描述

现在有两个好友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

输入：0.50

###################################################################

我的想法是，用动态规划，记录两个状态：0表示没有碰到蘑菇走到该位置的路线个数，1表示碰到蘑菇了，然后走到家，她不碰到蘑菇走到B的家的概率=她不碰到蘑菇走到B的家的路线个数/(总路线个数)=dp[-1][0]/(dp[-1][0]+dp[-1][1])

代码如下：

while 1:

    try:

        n,m,k=list(map(int,input().strip().split()))

        danger=[[False for _ in range(m)]for _ in range(n)]

        for _ in range(k):

            x,y=list(map(int,input().strip().split()))

            danger[x-1][y-1]=True

        if danger[0][0]:

            print('0.00')

            break

        dp=[[0,0]for _ in range(m+1)]

        dp[1]=[1,0]

        for row in range(1,n+1):

            for col in range(1,m+1):

                if danger[row-1][col-1]:

                    dp[col][1]+=dp[col-1][0]+dp[col-1][1]+dp[col][0]

                    dp[col][0]=0

                else:

                    dp[col][0]+=dp[col-1][0]

                    dp[col][1]+=dp[col-1][1]

        ans=dp[-1][0]/(dp[-1][0]+dp[-1][1])

        print(f'{ans:.2f}')

    except:

        break

####################

然后只通过了1/10.....

看测试案例，比如说

输入：

6 16 2

1 10

1 13

他的预期输出是1.00

我的输出是0.97

这怎么可能是1啊，难道是我题目理解有问题吗?

另外我有想到它这个1估计是每次都算一次概率值，然后pow（0.5，n）,n很大的时候就舍掉变成0了所以最后是1.....但是，我这个方法不应该更准确吗，求各位大佬帮忙看看~