#include<iostream> #include<cstring> #include<algorithm> using namespace std; int fx[] = {-2, -1, 1, 2, 2, 1, -1, -2}; int fy[] = {1, 2, 2, 1, -1, -2, -2, -1}; int tx,ty,ex,ey; unsigned long long f[30][30]; bool s[30][30]; int main(){ cin>>tx>>ty>>ex>>ey; tx+=2;ty+=2;ex+=2;ey+=2; f[2][2] = 1; s[ex][ey] = 1; for(int i=0;i<8;i++) s[ex+fx[i]][ey+fy[i]]=1; for(int i=2;i<=tx;i++){ for(int j=2;j<=ty;j++){ if(s[i][j])continue; f[i][j] = max(f[i][j],f[i-1][j]+f[i][j-1]); //状态转移方程 } } cout<<f[tx][ty]; return 0; } /*夭折的做法 #include<iostream> #include<cstring> #include<cmath> #define DEBUG 0 using namespace std; int n,p; class pp{public:unsigned long long x,y,w;pp(){x=y=w=0;}}walk[50]; int wnum; int map[30][30]={}; int housex,housey,targetx,targety; void f(){ //先检测每个p是否撞到 pp *t; for(int i=wnum-1;i>=0;i--){ //从最靠下的开始 t=walk+i; t->x+=1;//走一步 if(t->x<0 || t->y<0 || t->x>targetx || t->y>targety || map[t->x][t->y]!=0){ t->w=0; }else if(t->w>0 && i+1<wnum && map[t->x][walk[i+1].y]==0){ //然后下侧的w+1 if(DEBUG)cout<<t->x<<" "<<t->y<<"="; for(int ii=i+1;ii<wnum && map[t->x][walk[ii].y]==0;ii++){ if(DEBUG)cout<<ii<<"+"<<t->w<<" "; walk[ii].w+=t->w; } if(DEBUG)cout<<endl; } } if(DEBUG)cout<<endl; if(DEBUG)for(int i=0;i<wnum;i++)cout<<walk[i].y<<"="<<walk[i].w<<" "; if(DEBUG)cout<<endl; } void bookpos(int xx,int yy){ if(xx>=0 && yy>=0 && xx<30 && yy<30){ map[xx][yy]=1; } } int main() { cin>>targetx>>targety>>housex>>housey; wnum=targety+1; bookpos(housex-2,housey+1); bookpos(housex-2,housey-1); bookpos(housex-2,housey-2); bookpos(housex-1,housey+2); bookpos(housex-1,housey-2); bookpos(housex,housey); bookpos(housex+1,housey+2); bookpos(housex+1,housey+1); bookpos(housex+1,housey-2); bookpos(housex+2,housey+1); bookpos(housex+2,housey-1); if(DEBUG) for(int yy=0;yy<=targety;yy++){ for(int xx=0;xx<=targetx;xx++){ cout<<map[xx][yy]<<" "; } cout<<endl; } for(int i=0;i<wnum;i++){ walk[i].x=0; walk[i].y=i; walk[i].w= (map[0][i]==0); if(DEBUG)cout<<walk[i].w<<" "; } if(DEBUG)cout<<endl; int tt=targetx;while(tt--)f(); cout<<walk[targety].w<<endl; return 0; } */
https://www.luogu.com.cn/problem/P1002