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

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

蘑菇阵

  • 热度指数:1055时间限制:1秒空间限制:32768K
  • 本题知识点: 动态规划
  • 算法知识视频讲解

题目描述

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

输入描述:
  1. 第一行NMK(1 N,M 20, k 100),N,M为草地大小,接下来K行,每行两个整数xy,代表(x,y)处有一个蘑菇。
输出描述:
  1. 输出一行,代表所求概率(保留到2位小数)
输入例子:
  1. 2 2 1
  2. 2 1
输出例子:
  1. 0.50

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

  1. import java.util.*;
  2. public class Main{
  3. Scanner in = new Scanner(System.in);
  4. while(in.hasNext()){
  5. int n,m,k;
  6. String s1[] = in.nextLine().split(" ");
  7. n=Integer.parseInt(s1[0]);
  8. m=Integer.parseInt(s1[1]);
  9. k=Integer.parseInt(s1[2]);
  10. int [][]m=new int[n][m]={0};
  11. int [][]ret=new int[n][m];
  12. for(int i=0;i<k;i++){
  13. String[] s = in.nextLine().split(" ");
  14. int x,y;
  15. x=Integer.parseInt(s[0]);
  16. y=Integer.parseInt(s[1]);
  17. m[x-1][y-1]=1;
  18. }
  19. for(int i=0;i<n;i++){
  20. ret[i][m-1]=1;
  21. }
  22. for(int i=0;i<m;i++){
  23. ret[n-1][i]=1;
  24. }
  25. ret[n][m]=0;
  26. for(int i=n-2;i>=0;i--){
  27. for(int j=m-2;j>=0;j--){
  28. ret[i][j]=ret[i+1][j]+ret[i][j+1];
  29. }
  30. }
  31. }
  32. }

正确解题:

  1. //直接用概率进行DP,用路径数是不对的
  2. import java.util.Scanner;
  3. public class Main{
  4. public static void main(String[] args){
  5. Scanner sca = new Scanner(System.in);
  6. while(sca.hasNext()){
  7. int n = sca.nextInt();
  8. int m = sca.nextInt();
  9. int k = sca.nextInt();
  10. boolean[][] map = new boolean[n][m];
  11. for(int i = 0; i < k; i++) {
  12. int x = sca.nextInt()-1;
  13. int y = sca.nextInt()-1;
  14. map[x][y] = true;
  15. }
  16. double[][] cw = new double[n][m];
  17. cw[0][0] = 1;
  18. for(int i = 0; i < n; i++){
  19. for(int j = 0; j < m; j++){
  20. if(map[i][j]) cw[i][j] = 0;
  21. else if(i == 0 && j == 0) {}
  22. 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]));
  23. //System.out.print(String.format("%.5f",cw[i][j])+" ");
  24. }
  25. //System.out.println();
  26. }
  27. double res = cw[n-1][m-1];
  28. System.out.println(String.format("%.2f", res));
  29. }
  30. }
  31. }

发表评论

表情:
评论列表 (有 0 条评论,121人围观)

还没有评论,来说两句吧...

相关阅读

    相关 好久

    快过年了,正如老板所说一点过年的感觉都没有。 本想学期末把论文投出去,结果写专项用了二十多天,我真不知道这个论文节前能不能投出去?! 给自己点压力,希望

    相关 好久有读书

    你离快乐有多远? 你爱阅读吗?你知道自己离快乐有多远吗?作家池莉有个生动的比喻,她说:“如果把生活比喻为创作的意境,那么阅读就像阳光。”我们所追求的正是这一种阳光般的、