[CodeVS 1219]骑士游历

发布于 2017-07-12  1114 次阅读

做这题前真的很想吐槽一句CodeVS的天梯mmp，这题这么水的题目不放在过河卒后面却放在传纸条这种多线程DP后面真的是******
题目描述 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

这题没什么好说的，动态转移方程是

f[i][j]=f[i-2][j-1]+f[i-1][j-2]+f[i+2][j-1]+f[i+1][j-2] （注意判断边界）

注意递推的时候要纵列优先，否则无法算到往上走的情况。

哦对了，这题的f记得要long long，这几天CodeVS评测机卡的飞起，等了20多分钟才发现要long long 真是mmp

我的代码：

#include<cstdio>
#include<cstring>
int map[51][51],m,n,x1,y1,x2,y2;
long long f[51][51];
int main()
{
	scanf("%d%d%d%d%d%d",&n,&m,&y1,&x1,&y2,&x2);
	memset(f,0,sizeof(f));
	f[x1][y1]=1;
	for(int j=1;j<=m;j++)
	for(int i=1;i<=n;i++)
	{
		if(i>=2&&j>1) 
		f[i][j]+=f[i-2][j-1];
		if(i>=1&&j>2) 
		f[i][j]+=f[i-1][j-2];
		if(i+2<=n&&j>1) 
		f[i][j]+=f[i+2][j-1];
		if(i+1<=n&&j>2) 
		f[i][j]+=f[i+1][j-2];
	}
	printf("%lld\n",f[x2][y2]);
	return 0;
 }

 

等风来，不如追风去。