蘑菇阵使用路径数计算，想了好久没想出来，看答案才知道使用DP做的

傷城~ 2022-09-26 02:58 120阅读 0赞

蘑菇阵

*  热度指数：1055时间限制：1秒空间限制：32768K
 *  本题知识点： [动态规划][Link 1]
 *  [ 算法知识视频讲解][Link 2]

## 题目描述 ##

现在有两个好友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位小数)

##### 输入例子: #####

2 2 1
    2 1

##### 输出例子: #####

0.50

开始，想用路径数做，写了下面一半的程序：

import java.util.*;
    public class Main{
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n,m,k;
            String s1[] = in.nextLine().split(" ");
            n=Integer.parseInt(s1[0]);
            m=Integer.parseInt(s1[1]);
            k=Integer.parseInt(s1[2]);
            int [][]m=new int[n][m]={0};
            int [][]ret=new int[n][m];
            for(int i=0;i<k;i++){
                String[] s = in.nextLine().split(" ");
                int x,y;
                x=Integer.parseInt(s[0]);
                y=Integer.parseInt(s[1]);
                m[x-1][y-1]=1;
            }
            for(int i=0;i<n;i++){
                ret[i][m-1]=1;
            }
            for(int i=0;i<m;i++){
                ret[n-1][i]=1;
            }
            ret[n][m]=0;
            for(int i=n-2;i>=0;i--){
                for(int j=m-2;j>=0;j--){
                    ret[i][j]=ret[i+1][j]+ret[i][j+1];
                }
            }
            
        }
    }

正确解题：

//直接用概率进行DP，用路径数是不对的
    import java.util.Scanner;
      
    public class Main{
        public static void main(String[] args){
            Scanner sca = new Scanner(System.in);
            while(sca.hasNext()){
            int n = sca.nextInt();
            int m = sca.nextInt();
            int k = sca.nextInt();
            boolean[][] map = new boolean[n][m];
            for(int i = 0; i < k; i++) {
                int x = sca.nextInt()-1;
                int y = sca.nextInt()-1;
                map[x][y] = true;
            }
            double[][] cw = new double[n][m];
            cw[0][0] = 1;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    if(map[i][j]) cw[i][j] = 0;
                    else if(i == 0 && j == 0) {}
                    else cw[i][j] = (j-1<0?0:(i+1<n?cw[i][j-1]*0.5:cw[i][j-1]))+(i-1<0?0:(j+1<m?cw[i-1][j]*0.5:cw[i-1][j]));
                    //System.out.print(String.format("%.5f",cw[i][j])+" ");
                }
                //System.out.println();
            }
            double res = cw[n-1][m-1];
            System.out.println(String.format("%.2f", res));
            }
        }
    }

[Link 1]: http://www.nowcoder.com/questionCenter?questionTypes=000100&mutiTagIds=593
[Link 2]: http://www.nowcoder.com/courses/1