AcWing 5493. 过河卒
原题链接
简单
//动态规划
#include<iostream>
#define int long long
using namespace std;
const int N=25;
int endx,endy,hx,hy,dp[N][N],flag[N][N];
int dx[9]={0,1,2,2,1,-1,-2,-2,-1};
int dy[9]={0,2,1,-1,-2,2,1,-1,-2};
signed main(){
cin>>endx>>endy>>hx>>hy;
dp[0][0]=1;
for(int i=0;i<9;i++){
int xx=hx+dx[i],yy=hy+dy[i];
if(xx>=0&&xx<=endx&&yy>=0&&yy<=endy){
flag[xx][yy]=1;
}
}
int id=-1;
for(int i=1;i<=endx;i++){
if(flag[i][0]){
id=i;
break;
}
else dp[i][0]=1;
}
if(id!=-1){
for(int i=id;i<=endx;i++) flag[i][0]=1;
}
id=-1;
for(int i=1;i<=endy;i++){
if(flag[0][i]){
id=i;
break;
}
else dp[0][i]=1;
}
if(id!=-1){
for(int i=id;i<=endy;i++) flag[0][i]=1;
}
for(int j=1;j<=endy;j++){
for(int i=1;i<=endx;i++){
if(flag[i][j]) continue;
if(!flag[i-1][j]) dp[i][j]+=dp[i-1][j];
if(!flag[i][j-1]) dp[i][j]+=dp[i][j-1];
}
}
cout<<dp[endx][endy]<<endl;
return 0;
}