zoj 2271 Chance to Encounter a Girl <概率DP>

题目： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2271

题意：一个N*N的矩阵( N = 2*k-1 , k<=50) , 有一个 MM 站在矩阵的中央(k,k),MM 可以朝上下左右四个方向走动，不能走出去，

而 you 首先站在(0,k)的位置上，you每次只能向右走一步，求you遇到MM的概率~

思路： dp[t][x][y]  表示MM在t时刻到达坐标为 (x, y) 的概率，

　　　　那么 dp[t][x][y] = dp[t-1][x'][y']*p(x', y')  , p(x', y') 表示在坐标（x,'  y'）时走到坐标（x, y）的概率~

　　　　初始化 dp[0][k][k]=1; 

　

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int dir[ 4 ][ 2 ] = {1,0,0,1,-1,0,0,-1};
double dp[110][110][110];
int N;
double F( int x, int y )
{
    if( x<0||y>=N )return -1;
    if( (x==0&&y==0) || (x==0&&y==N-1)
       || (x==N-1&&y==0) || (x==N-1&&y==N-1))return 2.0;
    if( x==0 || y==0 || x==N-1 || y==N-1 ) return 3.0;
    return 4.0;
}
int main( )
{
    while(scanf("%d", &N)!= EOF){
        double ans=0;
        if(N%4==1){
            printf("%.4lf
", ans);
            continue;
        }
        memset(dp, 0, sizeof dp);

        dp[0][N/2][N/2]=1;

        for( int t=0; t<N; ++ t ){
        for( int i=0; i<N; ++ i ){
        for( int j=0; j<N; ++ j ){
            for(int k=0; k<4; ++ k){
                int x=i+dir[k][0], y=j+dir[k][1];
                if( F(x, y)>0 )
                    dp[t+1][i][j]+=dp[t][x][y]/F(x,y);
            }
            if( i==N/2 && j==t ){
                ans+=dp[t+1][i][j];
                dp[t+1][i][j]=0;
            }
        }
        }
        }
        printf("%.4lf
", ans);
   }
    return 0;
}