描述

编写一个程序，计算一个骑士从棋盘上的一个格子到另一个格子所需的最小步数。骑士一步可以移动到的位置由下图给出。

http://oj.xuanxiaoma.cn/api/public/img/bda6a5a0bfd84b74a89b0fa3fa4cc6输入描述

第一行给出骑士的数量 n。

在接下来的 3n 行中，每 3 行描述了一个骑士。其中，

第一行一个整数 L 表示棋盘的大小，整个棋盘大小为 L×L；

第二行和第三行分别包含一对整数 (x,y)，表示骑士的起始点和终点。假设对于每一个骑士，起始点和终点均合理。

输出描述

对每一个骑士，输出一行一个整数表示需要移动的最小步数。如果起始点和终点相同，则输出 0。

用例输入 1

3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1 用例输出 1

5 28 0 提示

对于 100% 的数据，有 4≤L≤300，保证 0≤x,y≤L−1。

#include <bits/stdc++.h>
using namespace std;
int n,l,x1,y,x2,y2;
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={-1,1,-2,2,-2,2,-1,1};
int bfs(){
	if(x1==x2&&y==y2){
		return 0;
	}
	queue<pair<pair<int,int>,int>> q;
	bool vis[l][l];
	for(int i=0;i<l;i++){
		for(int j=0;j<l;j++){
			vis[i][j]=0;
		}
	}
	q.push({{x1,y},0});
	vis[x1][y]=1;
	while(!q.empty()){
		int xx=q.front().first.first;
		int yy=q.front().first.second;
		int step=q.front().second;
		q.pop();
		for(int i=0;i<8;i++){
			int tx=xx+dx[i];
			int ty=yy+dy[i];
			if(tx>=0&&tx<l&&ty>=0&&ty<l&&!vis[tx][ty]){
				if(tx==x2&&ty==y2){
					return step+1;
				}
				vis[tx][ty]=1;
				q.push({{tx,ty},step+1});	
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	while(n--){
		cin>>l;
		cin>>x1>>y>>x2>>y2;
		cout<<bfs()<<'\n';
	}
	return 0;
}