算法:递归;
主要是越界问题;
1:
#include<iostream> using namespace std; int fx[9]={0,-1,1,-2,2,-2,2,-1,1}; int fy[9]={0,-2,-2,-1,-1,1,1,2,2}; bool s[40][40]={0}; long long f[25][25]; int main() {int n,m,x,y; cin>>n>>m>>x>>y;//n,m是B的;x,y是马的; for(int i=0;i<9;i++) s[x+fx[i]][y+fy[i]]=1;//把马和其所能达到的点 for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) if(!s[i][j]) { if(i==0&&j==0) f[0][0]=1; else if(i==0&&j>0) f[0][j]=f[0][j-1]; else if(j==0&&i>0) f[i][0]=f[i-1][0]; else f[i][j]=f[i-1][j]+f[i][j-1]; } cout<<f[n][m]<<endl; return 0; }
这个问题没有解决越界问题,(8,6,0,4)马的点为0时没有解决;
2:
#include<iostream> using namespace std; int fx[9]={0,-1,1,-2,2,-2,2,-1,1}; int fy[9]={0,-2,-2,-1,-1,1,1,2,2}; bool s[40][40]={0}; long long f[25][25]; int main() {int n,m,x,y; cin>>n>>m>>x>>y;//n,m是B的;x,y是马的; n+=2;m+=2;x+=2;y+=2; for(int i=0;i<9;i++) s[x+fx[i]][y+fy[i]]=1;//把马和其所能达到的点 f[2][1]=1; for(int i=2;i<=n;i++) for(int j=2;j<=m;j++) if(!s[i][j]) { f[i][j]=f[i-1][j]+f[i][j-1]; } cout<<f[n][m]<<endl; return 0; }
这个通过全部+2来解决越界问题;