摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
骑士游历 ★☆☆☆☆ 答案正确 100 2014/11/28 20:21:12 边界问题(50)

题意

在n*m的棋盘上,马只能从向右走日字格,求(x1,y1)到(x2,y2)的方案数。

题解

  • 还是很简单的棋盘动态规划了,还是注意边界问题,这题是从1开始的Σ( ° △ °|||)︴
dp[x][y]=dp[x][y]+dp[x-1][y-2]+dp[x-1][y+2]+dp[x-2][y-1]+dp[x-2][y+1];
  • 本题需要用64位整数,无需高精度

代码

1219.cpp代码已折叠
展开折叠内容
#include<cstdio>
unsigned long long dp[200][200]={};
int n,m,x0,y0,x1,y1;
int main()
{
    scanf("%d%d%d%d%d%d",&n,&m,&x0,&y0,&x1,&y1);
    dp[x0][y0]=1;
    for(int x=0;x<=m;++x)
        for(int y=0;y<=n;++y)
        {
            if(x>=2&&y>=3)
                dp[x][y]=dp[x-1][y-2];
            if(x>=2)
                dp[x][y]+=dp[x-1][y+2];
            if(x>=3&&y>=2)
                dp[x][y]+=dp[x-2][y-1];
            if(x>=3)
                dp[x][y]+=dp[x-2][y+1];
        }
    printf("%llu\n",dp[x1][y1]);
}

著作权声明[编辑]

关于[编辑]