小 （增加精度说明，增加转移方程，美化代码） |
小 （格式） |
||
| 第1行： | 第1行： | ||
[[分类:棋盘动态规划]] | [[分类:棋盘动态规划]] | ||
==摘要== | ==摘要== | ||
| − | {{信息题|骑士游历|http://www.codevs.cn/problem/1219/|1|100|time=2014/11/28 20:21:12 | + | {{信息题|骑士游历|http://www.codevs.cn/problem/1219/|1|100|time=2014/11/28 20:21:12|边界问题|50}} |
==题意== | ==题意== | ||
在n*m的棋盘上，马只能从向右走日字格，求(x1,y1)到(x2,y2)的方案数。 | 在n*m的棋盘上，马只能从向右走日字格，求(x1,y1)到(x2,y2)的方案数。 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 骑士游历 | ★☆☆☆☆ | 答案正确 | 100 | 2014/11/28 20:21:12 | 边界问题（50） |
在n*m的棋盘上，马只能从向右走日字格，求(x1,y1)到(x2,y2)的方案数。
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];
| 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]);
}
|
CloudLunar