输入包含多组数据。对于每组数据,第一行为草地大小。
接下来行,每行两个整数
,代表
处有一个蘑菇。
对于每组数据,输出一行,代表所求概率(保留到2位小数)
2 2 1 2 1 6 16 2 1 10 1 13
0.50 1.00
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            int n = scan.nextInt();
            int m = scan.nextInt();
            int k = scan.nextInt();
            int[][] map = new int[n+1][m+1];
            while(k != 0){
                int row = scan.nextInt();
                int col = scan.nextInt();
                map[row][col] = 1;
                k--;
            }
            
            double[][] dp = new double[n+1][m+1];
            dp[1][1] = 1.0;
            
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    if(!(i == 1 && j == 1)){
                        dp[i][j] = dp[i-1][j]*(j==m?1:0.5) + dp[i][j-1]*(i==n?1:0.5);
                    }
                    if(map[i][j] == 1){
                        dp[i][j] = 0;
                    }
                }
            }
            
            System.out.printf("%.2f",dp[n][m]);
            System.out.println();
        }
    }
} //动态规划的思想
import java.util.*;
public class Main{
    public static double dp(int[][] arr,int n,int m){
        double[][] res = new double[n+1][m+1];
        res[1][1] = 1.0;
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
//如果A不在(1,1)位置,此时他有两个方向可以走(向左或者向右),概率均为0.5
//在最后一列和最后一行的时候他只有一个方向可以走,所以概率为1.0                   if(!(i == 1 && j == 1)){
                    res[i][j] = res[i - 1][j] * (j == m ? 1.0 : 0.5) + res[i][j - 1] * (i == n ? 1.0 : 0.5);
                }
//如果arr[i][j]位置是蘑菇,则不可能走到该位置,所以该位置的概率为0.0
                if(arr[i][j] == 1){
                    res[i][j] = 0.0;
                }
            }
        }
        return res[n][m];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
             int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] arr = new int[n+1][m+1];
            int k = sc.nextInt();
            while(k != 0){
                int x = sc.nextInt();
                int y = sc.nextInt();
                arr[x][y] = 1;
                k--;
            }
                double result =  dp(arr,n,m);
                System.out.printf("%.2f\n",result);
             }
       
    }
}
 import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        while(input.hasNext()){
            int m = input.nextInt();
            int n = input.nextInt();
            int k = input.nextInt();
            int [][] mg=new int[m][n];
            for(int i=0; i<k; i++){
                int x= input.nextInt()-1;
                int y= input.nextInt()-1;
                mg[x][y]=1;
            }
            possibility(mg);
        }
        input.close();
    }
    
    public static void possibility(int [][]mg){
        int m=mg.length;
        int n=mg[0].length;
        //corner case:只有一行或者一列
        if(m==1||n==1){
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(mg[i][j]==1){
                        System.out.println("0.00");
                        return;
                    } 
                }
            }
             System.out.println("1.00");
             return;
        }
        
        double [][]pos=new double[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 && j==0)
                    pos[i][j]=1;
                else if(mg[i][j]==1)
                    pos[i][j]=0;
                else if(i==0)
                    pos[i][j]= 0.5*pos[i][j-1];
                else if(j==0)
                    pos[i][j]= 0.5*pos[i-1][j];
                else if(i==m-1&&j!=n-1)
                    pos[i][j]= pos[i][j-1]+0.5*pos[i-1][j];
                else if(i!=m-1&&j==n-1)
                    pos[i][j]= 0.5*pos[i][j-1]+pos[i-1][j];
                else if(i==m-1&&j==n-1)
                    pos[i][j]=pos[i][j-1]+ pos[i-1][j];
                else
                    pos[i][j]= 0.5*(pos[i][j-1]) + 0.5*(pos[i-1][j]); 
            }
        }
        System.out.printf("%.2f\n",pos[m-1][n-1]);
    }
}
package NewCoder.XiaoZhaoZhenTi; import java.util.Scanner; public class test2_3 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int N = scanner.nextInt(); int M = scanner.nextInt(); int K = scanner.nextInt(); int[][] matrix = new int[N][M]; for (int i = 0; i < K; i++) { int x = scanner.nextInt(); int y = scanner.nextInt(); matrix[x - 1][y - 1] = 1;// 有蘑菇 } double[][] noBomb = new double[N][M];// 记录没有蘑菇到达当前地点的概率 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (i == 0 && j == 0) { noBomb[i][j] = 1; continue; } if (matrix[i][j] == 0) { noBomb[i][j] = getResult(i - 1, j, N, M, noBomb) * getGaiLv(i - 1, j, N, M) + getResult(i, j - 1, N, M, noBomb) * getGaiLv(i, j - 1, N, M); // 等于左边无蘑菇到达概率*左边到当前过来的概率+等于上边无蘑菇的概率*上边过来的概率 } else { noBomb[i][j] = 0;// 有蘑菇,此点直接为0 } } } System.out.println(String.format("%.2f", noBomb[N - 1][M - 1])); } } public static double getResult(int x, int y, int N, int M, double matrix[][]) { if (x >= 0 && x < N && y >= 0 && y < M) { return matrix[x][y]; } else { return 0; } } public static double getGaiLv(int x, int y, int N, int M) { if (x == N - 1 || y == M - 1) { return 1;// 边界过来是1 } else { return 0.5;// 其余则是0.5过来的可能性 } } }
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int k = sc.nextInt();
			double[][] dp = new double[n + 1][m + 1];
			for (int i = 0; i < k; i ++ ) {
				dp[sc.nextInt()][sc.nextInt()] = 1;
			}
			dp[1][1] = 1;
			for (int i = 1; i <= n; i ++ ) {
				for (int j = 1; j <= m; j ++ ) {
					if(i == 1 && j == 1) continue;
					if(dp[i][j] == 1)
						dp[i][j] = 0;
					else {
						if(j == m && i != n)
							dp[i][j] = dp[i - 1][j] + dp[i][j - 1] * 0.5;
						else if(j != m && i == n)
							dp[i][j] = dp[i - 1][j] * 0.5 + dp[i][j - 1];
						else if(j == m && i == n)
							dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
						else
							dp[i][j] = dp[i - 1][j] * 0.5 + dp[i][j - 1] * 0.5;
					}
				}
			}
			System.out.println(String.format("%.2f", dp[n][m]));
		}
	}
}
import java.util.*; public class Main { public static void main(String[] args){ Scanner input = new Scanner(System.in); while(input.hasNext()){ int N = input.nextInt(); int M = input.nextInt(); int K = input.nextInt(); double[][] poss = new double[N][M]; boolean[][] mogu = new boolean[N][M]; poss[0][0] = 1; for(int i = 0; i < K; i++){ int a = input.nextInt(); int b = input.nextInt(); mogu[a-1][b-1] = true; } for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ if(mogu[i][j]){ poss[i][j] = 0; }else if(i != 0 && j != 0)){ poss[i][j] = (j==0?0:(i==N-1?1:0.5)*poss[i][j-1])+(i==0?0:(j==M-1?1:0.5)*poss[i-1][j]); } } } System.out.println(String.format("%.2f",poss[N-1][M-1])); } } }