动规做法

#include <iostream>
using namespace std;
int fx[10]={0,-2,-1,1,2,2,1,-1,-2};
int fy[10]={0,1,2,2,1,-1,-2,-2,-1};//移动
int bx,by,mx,my;
long long f[25][25];//dp
bool s[25][25];//地图
int main(){
    cin>>bx>>by>>mx>>my;
    //初始条件
	for(int i=0;i<=8;i++) if(mx+fx[i]>=0&&mx+fx[i]<=bx&&my+fy[i]>=0&&my+fy[i]<=by) 
		s[mx+fx[i]][my+fy[i]]=true;
	for(int i=0;i<=bx;i++){
		if(s[i][0]==false) f[i][0]=1;
		else break;
	}
    for(int i=0;i<=by;i++){
    	if(s[0][i]==false) f[0][i]=1;
    	else break;
	}
	//递推
    for(int i=1;i<=bx;i++){
    	for(int j=1;j<=by;j++){
        	if(s[i][j]==false) f[i][j]=f[i-1][j]+f[i][j-1];
		}
	}
	cout<<f[bx][by]<<endl;
    return 0;
}

再提供一种深搜做法

#include<bits/stdc++.h>
#define sc scanf
#define pr printf
#define int long long
using namespace std;
int bx,by;
int mx,my;
bool stop[25][25]={};
//马的控制点 
int Dx[9]={0,-2,-1,1,2,2,1,-1,-2};
int Dy[9]={0,1,2,2,1,-1,-2,-2,-1};
//走的方向 
int dp[25][25]={};
//dp表存数据 
int dfs(int x,int y){
	//dfs开始遍历 
	if(x<0||x>bx||y<0||y>by) return 0;
	if(stop[x][y]) return 0;
	//越界退出 
	if(dp[x][y]) return dp[x][y];
	//记忆化 
	int ii=0,jj=0;
	ii=dfs(x-1,y);
	jj=dfs(x,y-1);
	return dp[x][y]=ii+jj;
	//返回 + 存dp 
}
signed main(){
	sc("%lld%lld%lld%lld",&bx,&by,&mx,&my);
	
	for(int i=0;i<=8;i++) if(mx+Dx[i]>=0&&mx+Dx[i]<=bx&&my+Dy[i]>=0&&my+Dy[i]<=by) 
		stop[mx+Dx[i]][my+Dy[i]]=true;
	for(int i=0;i<=bx;i++)
		if(stop[i][0]==false) dp[i][0]=1;
		else break;
    for(int i=0;i<=by;i++)
    	if(stop[0][i]==false) dp[0][i]=1;
    	else break;
    //以上一坨都是初始化 
	dfs(bx,by);
	//倒着遍历 
	pr("%lld",dp[bx][by]);
	return 0;
}

思路

当前一格的路线是从左格和上格加下来的

代码1

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 25;
int x,y,n,m;
int a[N][N];
signed main(int argc, char **argv){
	cin >> n >> m >> x >> y;
	// 这里可以用方向数组优化
	a[x][y] = -1;
	a[x + 2][y + 1] = -1;
	a[x + 1][y + 2] = -1;
	if (x > 0)	a[x - 1][y + 2] = -1;
	if (x > 1)	a[x - 2][y + 1] = -1;
	if (x > 1 && y > 0)	a[x - 2][y - 1] = -1;
	if (x > 0 && y > 1)	a[x - 1][y - 2] = -1;
	if (y > 1)	a[x + 1][y - 2] = -1;
	a[x + 2][y - 1] = -1;
	a[0][0] = 1;
	for (int i = 0;i <= n;i++){
		for (int j = 0;j <= m;j++){
			if (a[i][j] == -1)	continue;
			if(i > 0)	a[i][j] += max(a[i - 1][j],0ll);
			if (j > 0)	a[i][j] += max(a[i][j - 1],0ll);
//			printf("i:%d j:%d %d\n",i,j,a[i][j]);
		}
	}
	cout << a[n][m];
	return 0;
}

代码2

#include <bits/stdc++.h>
#define int long long
using namespace std;
int x[] = {2,1,-1,-2,-2,-1,1,2},y[] = {1,2,2,1,-1,-2,-2,-1};
int a[25][25];
signed main(int argc, char **argv){
	int bx,by,mx,my;
	cin >> bx >> by >> mx >> my;
	// 也可以把边界++
	bx++,by++,mx++,my++; 
	a[1][1] = 1;
	a[mx][my] = -1;
	for (int i = 0;i < 8;i++){
		if(mx + x[i] > 0 && mx + x[i] <= bx && my + y[i] > 0 && my + y[i] <= by)
		a[mx + x[i]][my + y[i]] = -1;
	}
	for (int i = 1;i <= bx;i++){
		for (int j = 1;j <= by;j++){
			if (a[i][j] == -1)	continue;
			if (a[i - 1][j] != -1)	a[i][j] += a[i - 1][j];
			if (a[i][j - 1] != -1)	a[i][j] += a[i][j - 1];
		}
	}
	cout << a[bx][by];
	return 0;
}