笔试题算法系列（四）百度蘑菇阵

 1 import java.util.Scanner;
 2 
 3 public class Main{
 4     public static void main(String[] args){
 5         Scanner sc = new Scanner(System.in);
 6         String [] line;
 7         while(sc.hasNext()){
 8             line = sc.nextLine().split(" ");
 9             int n = Integer.parseInt(line[0]);
10             int m = Integer.parseInt(line[1]);
11             int k = Integer.parseInt(line[2]);
12             boolean[][] grid = new boolean[n+1][m+1];
13             double [][] p = new double[n+1][m+1];
14             for(int i=0; i<k; i++){
15                 line = sc.nextLine().split(" ");
16                 int x = Integer.parseInt(line[0]);
17                 int y = Integer.parseInt(line[1]);
18                 grid[x][y] = true;
19             }
20             for(int i=1; i<n+1; i++){
21                 for(int j=1; j<m+1; j++){
22                     if(i==1 && j==1){
23                         p[i][j] = 1;
24                         continue;
25                     }
26                     if(grid[i][j]){
27                         p[i][j] = 0;
28                         continue;
29                     }
30                     if(i==n && j ==m){
31                         p[i][j] = p[i][j-1]+p[i-1][j];
32                     }else if(i==n){
33                         p[i][j] = p[i][j-1]+p[i-1][j]*0.5;
34                     }else if(j==m){
35                         p[i][j] = p[i][j-1]*0.5 + p[i-1][j];
36                     }else{
37                         p[i][j] = p[i][j-1]*0.5 + p[i-1][j]*0.5;
38                     }
39                     
40                 }
41             }
42             System.out.println(String.format("%.2f", p[n][m]));
43         }
44         sc.close();
45     }
46 }