思路：刚开始dfs会超时，卒只能向下或者向右走。可递推出路径数的总和f[i][j]=f[i-1][j]+f[i][j-1]。 超时代码
#include<bits/stdc++.h> using namespace std; int a[21][21],vis[21][21],n,m,xx,yy,cnt=0; int dir[8][2]={{-2,-1},{-1,-2},{2,-1},{1,-2},{2,1},{1,2},{-1,2},{-2,1}}; int dr[2][2]={{0,1},{1,0}}; bool check(int x,int y) { if(vis[x][y]==0&&x>=0&&x<=n&&y>=0&&y<=m)return true; return false; } void dfs(int x,int y) { if(x==n&&y==m) { cnt++; return; } for(int i=0;i<2;i++) { int nx=dr[i][0]+x; int ny=dr[i][1]+y; if(check(nx,ny)) { vis[nx][ny]=1; dfs(nx,ny); vis[nx][ny]=0; } } } int main() { cin>>n>>m>>xx>>yy; memset(vis,0,sizeof(vis)); for(int i=0;i<8;i++) { int nx=xx+dir[i][0]; int ny=yy+dir[i][1]; if(nx>=0&&nx<=n&&ny>=0&&ny<=m&&vis[nx][ny]==0) vis[nx][ny]=1; } vis[xx][yy]=1; vis[0][0]=1; // for(int i=0;i<=n;i++) // { // for(int j=0;j<=m;j++) // cout<<vis[i][j]; // cout<<endl; // } dfs(0,0); cout<<cnt<<endl; return 0; }递推
#include<bits/stdc++.h> using namespace std; int vis[21][21],n,m,xx,yy; int dir[8][2]={{-2,-1},{-1,-2},{2,-1},{1,-2},{2,1},{1,2},{-1,2},{-2,1}}; bool check(int x,int y) { if(vis[x][y]==0&&x>=0&&x<=n&&y>=0&&y<=m)return true; return false; } long long f[21][21]; int main() { cin>>n>>m>>xx>>yy; memset(vis,0,sizeof(vis)); for(int i=0;i<8;i++) { int nx=xx+dir[i][0]; int ny=yy+dir[i][1]; if(nx>=0&&nx<=n&&ny>=0&&ny<=m&&vis[nx][ny]==0) vis[nx][ny]=1; } vis[xx][yy]=1; vis[0][0]=1; for(int i=1;i<=n;i++) if(vis[i][0])break; else f[i][0]=1; for(int i=1;i<=m;i++) if(vis[0][i])break; else f[0][i]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(check(i,j)) { f[i][j]=f[i-1][j]+f[i][j-1]; } } } cout<<f[n][m]<<endl; return 0; }