$des$
实现一个bfs
$sol$
写了一个双向bfs
#includeusing namespace std;#define Rep(i, a, b) for(int i = a; i <= b; i ++)#define gc getchar()inline int read() { int x = 0; char c = gc; while(c < '0' || c > '9') c = gc; while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}const int N = 305;const int xd[] = {-1, -2, -2, -1, 1, 2, 2, 1};const int yd[] = {-2, -1, 1, 2, 2, 1, -1, -2};int Lim = 300;int vis[N][N], bel[N][N];int n;int Bfs_time;queue > Q;inline int Work(int sx, int sy, int tx, int ty) { if(sx == tx && sy == ty) return 0; memset(vis, 0, sizeof vis); memset(bel, 0, sizeof bel); while(!Q.empty()) Q.pop(); Q.push(make_pair(sx, sy)); Q.push(make_pair(tx, ty)); bel[sx][sy] = 1, bel[tx][ty] = 2; vis[tx][ty] = 1; while(!Q.empty()) { pair tp = Q.front(); Q.pop(); int px = tp.first, py = tp.second; Rep(i, 0, 7) { int nx = px + xd[i], ny = py + yd[i]; if(bel[nx][ny] == bel[px][py] || nx < 0 || nx > Lim || ny < 0 || ny > Lim) continue; if(vis[nx][ny]) return vis[nx][ny] + vis[px][py]; vis[nx][ny] = vis[px][py] + 1; bel[nx][ny] = bel[px][py]; Q.push(make_pair(nx, ny)); } }}int main() { n = read(); while(n --) { Lim = read(); cout << Work(read(), read(), read(), read()) << "\n"; } return 0;}