首页 > 代码库 > codevs 1219 骑士游历 1997年
codevs 1219 骑士游历 1997年
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
设有一个n*m的棋盘（2≤n≤50，2≤m≤50），如下图，在棋盘上有一个中国象棋马。
规定：
1)马只能走日字
2)马只能向右跳
问给定起点x1,y1和终点x2,y2，求出马从x1,y1出发到x2,y2的合法路径条数。
输入描述 Input Description
第一行2个整数n和m
第二行4个整数x1,y1,x2,y2
输出描述 Output Description
输出方案数
样例输入 Sample Input
30 30
1 15 3 15
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
2<=n,m<=50
棋盘dp
搞法一 记忆化搜索
#include <iostream>#include <cstdio>int n,m,x1,y1,x2,y2;long long dp[55][55];long long dfs(int x,int y){ if(x==x2&&y==y2) return 1; if(y>n||y<=0) return 0; if(x>x2) return 0; long long ans=0; if(dp[x][y]>0) return dp[x][y]; ans+=dfs(x+1,y+2); ans+=dfs(x+2,y+1); ans+=dfs(x+2,y-1); ans+=dfs(x+1,y-2); dp[x][y]=ans; return ans;}int main(){ scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2); std::cout<<dfs(x1,y1); return 0;}
搞法二 dp
#include <cstdio>long long dp[55][55];int n,m,x1,x2,y1,y2;int main(){ scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2); dp[y1][x1]=1; for(int x=x1;x<=x2;x++) { for(int y=1;y<=n;y++) { if(y-1>0) dp[y][x]+=dp[y-1][x-2]; if(y-2>0) dp[y][x]+=dp[y-2][x-1]; if(y-n<0) dp[y][x]+=dp[y+1][x-2]; if(y-n+1<0) dp[y][x]+=dp[y+2][x-1]; } } printf("%d",dp[y2][x2]); return 0;}
codevs 1219 骑士游历 1997年
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。