题意补充：“骑士”的移动方式与中国象棋中的“马”类似，即在一个方向移动 $2$ 格，另一个方向移动 $1$ 格。

难度： 绿

算法： 搜索，最短路

显然，这题一定有解。

在有解的基础上建立以下几个假设：

记 $f(x_1,y_1,x_2,y_2)$ 为从 $(x_1,y_1)$ 移至 $(x_2,y_2)$ 的最小费用。

1.$f(x_1,y_1,x_2,y_2)=f(x_1+x,y_1+y,x_2+x,y_2+y)$，$x,y$ 为任意整数。

2. $f(x_1,y_1,x_2,y_2)=f(x_2,y_2,x_1,y_1)$

3. $f(x_1,y_1,x_2,y_2)=f(x_1,y_1,-x_2,y_2)=f(x_1,y_1,x_2,-y_2)$

以每个点为一个结点，以该节点可以直接移动到的点之间连一条边。

以$(2,2)$ 为出发点（不要写成 $(0,0)$）跑单源最短路。对于每次询问，利用以上性质将出发点修改为 $(2,2)$ ，然后直接输出距离即可。（第二条性质好像没用到）

#include<bits/stdc++.h>
using namespace std;
int mp[310][310],m=0,u,v,w,dis[100010],vis[100010]={},fx[8]={1,1,-1,-1,2,2,-2,-2},fy[8]={2,-2,2,-2,1,-1,1,-1},x,y,t,d[5];
struct node{
	int u,dis;
	bool operator > (const node& a) const {return dis>a.dis;}
}k;
vector<int> e[200010];
priority_queue<node,vector<node>,greater<node> > q;
void build(int a,int b){
	e[a].push_back(b);
	return ;
}
int main(){
	memset(dis,0x3f3f3f,sizeof(dis));
	k.dis=1;
	for(int i=0;i<=302;i++){
		for(int j=0;j<=302;j++){
			mp[i][j]=++m;
		}
	}
	for(int i=0;i<=302;i++){
		for(int j=0;j<=302;j++){
			for(int k=0;k<8;k++){
				x=i+fx[k],y=j+fy[k];
				if(x>=0&&y>=0&&x<=302&&y<=302){
					e[mp[i][j]].push_back(mp[x][y]);
				}
			}
		}
	}
	dis[mp[2][2]]=0;
	k.u=mp[2][2],k.dis=0;
	q.push(k);
	while(!q.empty()){
		u=q.top().u;
		q.pop();
		if(vis[u]==1) continue;
		vis[u]=1;
		for(int i=0;i<int(e[u].size());i++){
			v=e[u][i];
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				k.u=v,k.dis=dis[v];
				q.push(k);
			}
		}
	}
	scanf("%d",&t);
	while(t--){
		for(int i=0;i<=4;i++) scanf("%d",&d[i]);
		d[3]=abs(d[3]-d[1]),d[4]=abs(d[4]-d[2]);
		d[3]+=2,d[4]+=2;
		printf("%d\n",dis[mp[d[3]][d[4]]]);
	}
	return 0;
}