模拟队列 + BFS(广度优先遍历)
#include <iostream>
#include <cstring>
using namespace std;
int T, n;
const int N = 310;
int g[N][N];
int d[N][N];
int dx[] = {-2, -2, -1, -1, 2, 2, 1, 1}, dy[] = {-1, 1, -2, 2, -1, 1,-2, 2};
int bfs(pair<int, int>& s, pair<int, int>& e)
{
pair<int, int> q[N * N];
memset(d, -1, sizeof d);
int hh = 0, tt = -1;
q[++ tt] = s;
d[s.first][s.second] = 0;
while(hh <= tt)
{
pair<int, int> t = q[hh ++];
bool flag = false;
for (int i = 0; i < 8; i ++)
{
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && x <= n && y >= 0 && y <= n && d[x][y] == -1)
{
d[x][y] = d[t.first][t.second] + 1;
if (x == e.first && y == e.second)
{
flag = true;
break;
}
q[++ tt] = {x, y};
}
}
if (flag) break;
}
return d[e.first][e.second];
}
int main(void)
{
cin >> T;
while (T --)
{
cin >> n;
pair<int, int> s, e;
cin >> s.first >> s.second;
cin >> e.first >> e.second;
cout << bfs(s, e) << endl;
}
return 0;
}