1219 骑士游历
题目描述 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
#include<stdio.h>
#include<string.h>
#include<math.h>
long long a[100][100];
int main()
{
int i,j,sx,sy,ex,ey,n,m,x,y;
scanf("%d %d",&n,&m);
scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
a[sx][sy]=1;
for(x=1;x<=n;x++)
{
for(y=1;y<=m;y++)
{//每一步的具体判断，，判断其是否超界
if(x-2>=1&&y-1>=1) a[x][y]+=a[x-2][y-1];
if(x-1>=1&&y-2>=1) a[x][y]+=a[x-1][y-2];
if(x-1>=1&&y+2<=m) a[x][y]+=a[x-1][y+2];
if(x-2>=1&&y+1<=m) a[x][y]+=a[x-2][y+1];
}
}
printf("%lld",a[ex][ey]);//打表，动态规划
return 0;
}第二种解法：
#include<cstdio>
int main()
{
long long dp[55][55]={0};int n,m,x,y,a,b;
scanf("%d %d %d %d %d %d",&n,&m,&x,&y,&a,&b);
dp[x][y]=1;
for(int i=x+1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j]=dp[i-2][j-1]+dp[i-2][j+1]+dp[i-1][j-2]+dp[i-1][j+2];
printf("%lld",dp[a][b]);
}
你可能会问，为什么不判断其是否越界，，因为即使其越界了，，因为是二维数组，所以其越界了值也会为0，，这就是为什么其I=x+1而不是从0开始的原因了，而且这也提高了效率！
第三种： 目前没看懂
#include<cstdio>
int n,m,a,b,c,d,vis[55][55],way[4][2]={{2,1},{1,2},{1,-2},{2,-1}};
long long f[55][55],need[55][55];
void go(int x,int y)
{
if(x>=c) return ;
long long now=f[c][d];
if(need[x][y])
{
f[c][d]+=need[x][y];
return;
}
for(int i=0;i<4;i++)
if(x+way[i][0]<=n&&x+way[i][0]>0&&y+way[i][1]<=m&&y+way[i][1]>0&&!vis[x+way[i][0]][y+way[i][1]])
{
vis[x+way[i][0]][y+way[i][1]]=1;
f[x+way[i][0]][y+way[i][1]]++;
go(x+way[i][0],y+way[i][1]);
vis[x+way[i][0]][y+way[i][1]]=0;
}
need[x][y]=f[c][d]-now;
}
int main()
{
scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d);
vis[a][b]=1;
f[a][b]=1;
go(a,b);
printf("%lld",f[c][d]);
return 0;
}