Vijos 1121 马拦过河卒

时间:2024-01-04 20:18:56

首先要看清题目,卒只能向右或者向下走。而不是四周转。这样的话就无解了。

定义f[i][j],表示走到(i,j)这个点时的总步数。这样就写出了一个递推公式f[i][j]=f[i-1]+f[i][j-1]。因为卒是从(0,0)出发,所以f[0][0]=1,因为 f[i][j]只能从前一个状态转移过来。所以在转移前需要加特判即(i-1,j)和(i,j-1)两点不是马所控制的点。所以在递推之前还应有一个预处理。来处理马所能控制的点,预处理很好写。剩下的没有什么了。输出目标节点的 f 值即可。

代码:

#include<iostream>
#include<cstdio>
using namespace std;
int x1,y1,x2,y2;
int f[][],a[][],ans;
int mx[]={,,,,-,-,-,-};
int my[]={,,-,-,-,-,,};
int main()
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
a[x2][y2]=;
for(int i=;i<=;i++){
if(x2+mx[i]<=x1&&y2+my[i]<=y1)
a[x2+mx[i]][y2+my[i]]=;
}
f[][]=;
for(int i=;i<=x1;i++)
for(int j=;j<=y1;j++){
if(i>&&!a[i-][j])
f[i][j]+=f[i-][j];
if(j>&&!a[i][j-])
f[i][j]+=f[i][j-];
}
printf("%d",f[x1][y1]);
}