（以“分类:棋盘动态规划 ==摘要== {{信息题|骑士游历|http://www.codevs.cn/problem/1219/|1|100|time=2014/11/28 20:21:12|50|边界问题}} ==题意== 在n...”为内容创建页面） |
小 （格式） |
||
| （未显示1个用户的1个中间版本） | |||
| 第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)的方案数。 | ||
| 第7行： | 第7行： | ||
*还是很简单的棋盘动态规划了，还是注意边界问题，这题是从1开始的Σ( ° △ °|||)︴ | *还是很简单的棋盘动态规划了，还是注意边界问题，这题是从1开始的Σ( ° △ °|||)︴ | ||
<pre> | <pre> | ||
| + | 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]; | ||
</pre> | </pre> | ||
| + | *本题需要用64位整数，无需高精度 | ||
==代码== | ==代码== | ||
{{折叠|1219.cpp代码已折叠 | {{折叠|1219.cpp代码已折叠 | ||
| 第22行： | 第24行： | ||
{ | { | ||
if(x>=2&&y>=3) | if(x>=2&&y>=3) | ||
| − | dp[x][y]= | + | dp[x][y]=dp[x-1][y-2]; |
if(x>=2) | if(x>=2) | ||
| − | + | dp[x][y]+=dp[x-1][y+2]; | |
if(x>=3&&y>=2) | if(x>=3&&y>=2) | ||
| − | + | dp[x][y]+=dp[x-2][y-1]; | |
if(x>=3) | if(x>=3) | ||
| − | + | dp[x][y]+=dp[x-2][y+1]; | |
} | } | ||
printf("%llu\n",dp[x1][y1]); | printf("%llu\n",dp[x1][y1]); | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 骑士游历 | ★☆☆☆☆ | 答案正确 | 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