【概率】【找规律】hdu6229 Wandering Robots

题意：一个机器人在正方形迷宫的左上角，迷宫里有些格子有障碍物，每一步机器人会等概率地向能走的格子转移（包含自身）。问你无限长的时间之后，机器人处于矩形对角线的右下方的概率。

无限长时间意味着，起点没有了意义。只需统计右下方每个格子的贡献之和比上所有格子的贡献之和。

假设迷宫不是离散的，而是连续的，那么概率就是右下方的面积比上正方形的总面积。

然而，因为迷宫是离散的，而且有坏点存在，也就意味着会有“边缘效应”存在，边缘处的贡献会降低。假设最开始中间每个格子贡献为5（有五个格子可以转移到它），边缘为4，角落为3。再扣去坏点的损失，直接用右下方之和比上所有之和就是答案了。

#include<cstdio>

#include<algorithm>

using namespace std;

int T,n,K;

int x[1005],y[1005];

typedef long long ll;

const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

bool a[10005][10005];

int main(){

    scanf("%d",&T);

    for(int zu=1;zu<=T;++zu){

        scanf("%d%d",&n,&K);

        ll ans=(ll)(n-2)*(ll)(5*n+6)+12ll;

        ll ans2=(ans-5ll*(ll)n+4ll)/2ll+5ll*(ll)n-4ll;

        for(int i=1;i<=K;++i){

            scanf("%d%d",&x[i],&y[i]);

            a[x[i]][y[i]]=1;

        }

        for(int i=1;i<=K;++i){

            int cnt=0;

            for(int j=0;j<4;++j){

                int tx=x[i]+dx[j],ty=y[i]+dy[j];

                if(tx>=0 && tx<n && ty>=0 && ty<n){

                    ++cnt;

                    if(!a[tx][ty]){

                        --ans;

                        if(tx+ty>=n-1){

                            --ans2;

                        }

                    }

                }

            }

            ans-=(ll)(cnt+1);

            if(x[i]+y[i]>=n-1){

                ans2-=(ll)(cnt+1);

            }

        }

        printf("Case #%d: %lld/%lld\n",zu,ans2/__gcd(ans2,ans),ans/__gcd(ans2,ans));

        for(int i=1;i<=K;++i){

            a[x[i]][y[i]]=0;

        }

    }

    return 0;

}

巴特西

【概率】【找规律】hdu6229 Wandering Robots

最新文章

热门文章