首页 > 代码库 > 1219 骑士游历（棋盘DP）
1219 骑士游历（棋盘DP）
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
分类标签 Tags 点此展开
动态规划 棋盘型DP 1997年
代码
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>using namespace std;long long f[101][101];int n,m,x1,x2,y1,y2;int main(){ scanf("%d%d",&n,&m); scanf("%d%d%d%d",&x1,&y1,&x2,&y2); f[x1][y1]=1;//显然，当前所在点的途径只有1 for(int i=x1;i<=n;i++)//从当前所在点开始 for(int j=1;j<=m;j++) { if(i-2>0&&j-1>0) f[i][j]+=f[i-2][j-1]; if(i-2>0&&j+1<=m) f[i][j]+=f[i-2][j+1]; if(i-1>0&&j-2>0) f[i][j]+=f[i-1][j-2]; if(i-1>0&&j+2<=m) f[i][j]+=f[i-1][j+2]; } cout<<f[x2][y2]; return 0;}
注意：在赋初值的时候一定要注意赋哪个！！
思路：还记得过河卒吗？
这个题和那个题的思路是一样的！
由于马只能走日而且只能从左边来，所以要判断4种情况，他从（-2,1）（-2，-1）（-1,2）（-1，-2）这4个地方来，
但还要判断他是否出界！！！
所以该点的方案数就是这4个点的方案数的和！
1219 骑士游历（棋盘DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。