#include<iostream> #include<algorithm> using namespace std; //协助计算马所能到达点 int fx[9]={0,-2,-1,1,2,2,1,-1,-2},fy[9]={0,1,2,2,1,-1,-2,-2,-1}; int ax,ay,mx,my; long long ans; long long f[30][30]; bool v[30][30]; int main() { freopen("pj024.in","r",stdin); freopen("pj024.out","w",stdout); cin>>ax>>ay>>mx>>my; ax++;ay++;mx++;my++; //设置原点的路径数为1 f[1][1]=1; //标记马所能走到的点 v[mx][my]=1; for(int i=1;i<=8;i++) v[mx+fx[i]][my+fy[i]]=1;
for(int i=1;i<=ax;i++) for(int j=1;j<=ay;j++) { //如果是马能走到的点,则跳过此次循环 if(v[i][j])continue; //如果不是,则将能到达该点的路径数赋值为能到达它左边那点的路径数和能到达它上面那点的路径数之和(典型dp思想) f[i][j]=max(f[i][j],f[i-1][j]+f[i][j-1]); } //最终输出能到达B点的路径数 cout<<f[ax][ay]; cin>>ax; return 0; }
题目78 [NOIP 2002]过河卒
1
评论
2022-07-18 15:10:01
|