A21810.过河卒 题解

这是一道动态规划的题目，当然也可以用广度优先搜索来做。
广度优先搜索太水了，这里只出示动态规划。
本题要判断马能走到的位置，所以这里定义一个flag去标记马的位置，
还有越界问题，需要判断，这里不一一讲解，直接上代码。

#include<bits/stdc++.h>
using namespace std;
int n,m,s1,s2;
long long dp[25][25];
bool flag[25][25];//标记马能到达的位置
int d[8][2]={1,2,1,-2,-1,2,-1,-2,2,1,2,-1,-2,1,-2,-1};
int main(){
	cin>>n>>m>>s1>>s2;
	n+=2,m+=2,s1+=2,s2+=2;//防止越界，因为马的偏移量是2
	dp[2][2]=1;
	flag[s1][s2]=1;
	for(int i=0;i<8;i++){
		int xx=s1+d[i][0];
		int yy=s2+d[i][1];
		if(xx>=2&&xx<=n&&yy>=2&&yy<=m){
			flag[xx][yy]=1;
			dp[xx][yy]=0;
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=2;j<=m;j++){
			if(flag[i][j]){
				continue;
			}
			dp[i][j]=max(dp[i][j],dp[i-1][j]+dp[i][j-1]);
		}
	}
	cout<<dp[n][m];
	return 0;
}

其实还有一种更简单的方法，上代码。

#include<bits/stdc++.h>
using namespace std;
int n,m,s1,s2;
long long dp[25][25];
bool flag[25][25];
int d[8][2]={1,2,1,-2,-1,2,-1,-2,2,1,2,-1,-2,1,-2,-1};
int main(){
	cin>>n>>m>>s1>>s2;
	n++,m++,s1++,s2++;
	dp[1][1]=1;
	flag[s1][s2]=1;
	for(int i=0;i<8;i++){
		int xx=s1+d[i][0];
		int yy=s2+d[i][1];
		if(xx>=1&&yy>=1){
			flag[xx][yy]=1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(flag[i][j]){
				continue;
			}
			dp[i][j]+=dp[i-1][j]+dp[i][j-1];
		}
	}
	cout<<dp[n][m];
	return 0;
}