CodeVS/1219 2014年11月28日 (五) 21:07云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
骑士游历	★☆☆☆☆	答案正确	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]); }