【题目描述】 传送门
【题解】
大范围贪心，然后小范围BFS，为了答案准确，尽量使这个小范围大，这题100就可以了。
代码如下
#include<queue> #include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int f[8][2]={{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}}; int x,y,ans; bool vis[105][105]; struct xcw{int x,y,t;}; queue<xcw> que; int ads(int x){return x<0?-x:x;} bool check(int x,int y){if(x<0||x>100||y<0||y>100)return 0;return !vis[x][y];} void Work(int x,int y,int t){vis[x][y]=1;que.push((xcw){x,y,t});} int BFS(int x,int y){ que.push((xcw){x,y,0});vis[x][y]=1; while(!que.empty()){ x=que.front().x,y=que.front().y;int t=que.front().t;que.pop(); for(int i=0;i<8;i++) if(check(x+f[i][0],y+f[i][1])){ Work(x+f[i][0],y+f[i][1],t+1); if(x+f[i][0]==50&&y+f[i][1]==50) return t+1; } } } int main(){ int x1,y1; scanf("%d%d%d%d",&x,&y,&x1,&y1); x=ads(x-x1);y=ads(y-y1); while(x+y>=50){ if(x<y) swap(x,y); if(x-4>=2*y) x-=4;else x-=4,y-=2; ans+=2; } x+=50,y+=50; if(x<y) swap(x,y); printf("%d\n",BFS(x,y)+ans); return 0; }