smzx 骑士 题解

· · 题解

记忆化搜索+概率。

用 dfs(x,y,step) 表示当前骑士在 (x,y) 的位置上，走 step 步后仍在棋盘上的概率。

一个骑士一步可以跳 8 个不同的位置，所以走 step 步后的概率等于一步能跳到的 8 个位置中，每个位置走 step-1 步后在棋盘上的概率乘 \frac{1}{8}。

可得 dfs(x,y,step)=dfs(x-2,y-1,step-1)\times\frac{1}{8}+dfs(x-2,y+1,step-1)\times\frac{1}{8}+\cdots

边界条件：当 step=0 时，返回 1。

记得记忆化。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=110,XY=20,F=10;
int g,x,y,n,fx[F]={0,-2,-2,-1,1,2,2,1,-1,},fy[F]={0,-1,1,2,2,1,-1,-2,-2};
double dp[XY][XY][N];
bool r[XY][XY][N];
double dfs(int dx,int dy,int step)//记忆化搜索
{
    int tx,ty;
    if(!step) return 1;//边界返回
    if(r[dx][dy][step]) return dp[dx][dy][step];//记忆化返回
    for(int i=1;i<=8;i++)//求递推式
    {
        tx=dx+fx[i],ty=dy+fy[i];
        if(tx>=1&&tx<=8&&ty>=1&&ty<=8) dp[dx][dy][step]+=dfs(tx,ty,step-1)*0.125;
    }
   //记忆化
    r[dx][dy][step]=true;
    return dp[dx][dy][step];
}
int main()
{
    scanf("%d",&g);
    while(g--)
    {
        scanf("%d%d%d",&x,&y,&n);
        //多测清空
        for(int i=1;i<=x;i++)
        {
            for(int j=1;j<=y;j++)
            {
                for(int k=1;k<=n;k++) r[i][j][k]=false,dp[i][j][k]=0;
            }
        }
        printf("%lf\n",dfs(x,y,n));
    }
    return 0;
}