동적 기획-바이두-버섯진

현재 두 명의 친구 A와 B가 있는데 버섯이 자란 nüm의 네모난 잔디밭에 살고 있다. A재(1,1), B재(n,m).현재 A는 B를 방문하고 싶은데 B의 집만 가고 싶어서 매번 (i, j+1) 또는 (i+1, j) 같은 노선만 걷는다. 잔디밭에 k개의 버섯이 칸에 심어져 있다(i, 여러 개의 버섯이 같은 칸에 있을 수 있다). A는 한 걸음 한 걸음 무작위로 선택하면 (그녀가 경계에 있으면 한 가지 선택밖에 없다) 버섯을 만나지 않고 B의 집에 갈 확률이 얼마나 됩니까?
설명 입력:
첫 번째 줄 N, M, K (2≤N, M≤20, k≤100), N, M은 잔디 크기이고 다음 K 줄은 줄마다 두 개의 정수 x, y, 대표 (x, y)에 버섯이 있다.
출력 설명: 한 줄을 출력하여 원하는 확률(2자리 소수까지 보류)을 나타냅니다. 입력 예: 2 2 1 2 1 출력 예: 0.50
사고방식: 잘못된 해법: 첫 번째 반응 사고방식은 경로를 이용하여 하는 것이다. 갈 수 있는 경로/전체 경로를 이용하여 AC를 할 수 없다. 자세히 생각한 후에 경로가 전혀 같은 확률이 아니라는 것을 발견했다. 예를 들어 다음과 같다. 1 2 3 4 5 6
1-2:0.5, 2-3:0.5 3-6:1 그러므로 1-2-3-6 확률은:0.25이다.1-4:0.5, 4-5:1,5-6:1 따라서 1-4-5-6 확률은 0.5.경로에는 확률이 같지 않은 상황이 존재할 수 있다.정확한 사고방식: 사용 확률 dp.dp[i][j]는 (0,0)에서 (i,j) 사이의 확률이 얼마인지를 나타낸다.dp의 구체적인 상황은 대체로 세 가지가 있다.i, j가 모두 0일 때 dp[i][j]=1;2. i와 j가 버섯의 위치일 때 dp[i][j]=0;3. 세 번째 상황은 바로 우리의 추이 상황이다. 여기서 특히 경계를 주의해야 한다. 경계를 고려하지 않으면 다음과 같은 것을 얻을 수 있다. dp[i][j]=dp[i-1][j]*0.5+dp[i][j-1]*0.5;맨 오른쪽이나 맨 아래에 있을 때 0.5를 곱하지 않아도 된다. 상황에 따라 판단하면 다음은 완전한 판단이다.

  dp[i][j]=(i-1<0?0:(j+1>=m?dp[i-1][j]:dp[i-1][j]*0.5))+(j-1<0?0:(i+1>=n?dp[i][j-1]:dp[i][j-1]*0.5));

구체적인 자바 코드는 다음과 같다.

package company;

import java.util.Scanner;

/** *        A B，          n＊m        ，A (1,1),B (n,m)。  A    B，      B  ， *         (i,j+1) (i+1,j)     ，     k        (           ), ：A        *     (      ，       )，          B        ？ * Created by lizhaoz on 2016/4/15. */

public class Mushroom {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();
            boolean[][] map=new boolean[n][m];
            for (int i = 0; i < k; i++) {
                int x=in.nextInt()-1;
                int y=in.nextInt()-1;
                map[x][y]=true;
            }
            double[][] dp=new double[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (i==0&&j==0){
                        dp[i][j]=1.0;
                    }
                    else if (map[i][j]==true){
                        dp[i][j]=0;
                    }else {
                        dp[i][j]=(i-1<0?0:(j+1>=m?dp[i-1][j]:dp[i-1][j]*0.5))+(j-1<0?0:(i+1>=n?dp[i][j-1]:dp[i][j-1]*0.5));
                    }
                }
            }
            System.out.println(String.format("%.2f",dp[n-1][m-1]));
        }

    }
}