Pascal(fpc 3.0.2) 解法, 执行用时: 310ms, 内存消耗: 1144K, 提交时间: 2019-11-02 22:48:51

var
  a,b:array[0..301,0..301] of longint;
  h:array[0..10000001,1..2] of longint;
  u:array[1..8] of longint=(2,1,-1,-2,-2,-1,1,2);
  v:array[1..8] of longint=(-1,-2,-2,-1,1,2,2,1);
  a1,b1,c,d,i,n,m:longint;
procedure q;
var
  t,w,i,j,x,y:longint;
begin
  for i:=0 to m do
   for j:=0 to m do a[i,j]:=b[i,j];
  a[a1,b1]:=1;
  h[1,1]:=a1;
  h[1,2]:=b1;
  t:=1;
  w:=1;
  repeat
   for i:=1 to 8 do
    begin
     x:=h[t,1]+u[i];
     y:=h[t,2]+v[i];
     if (x>=0)and(y>=0)and(x<=m)and(y<=m)and(a[x,y]=0) then
      begin
       w:=w+1;
       h[w,1]:=x;
       h[w,2]:=y;
       a[x,y]:=a[h[t,1],h[t,2]]+1;
       if (x=c)and(y=d) then begin writeln(a[x,y]-1);exit;end;
      end;
    end;
   t:=t+1;
  until t>w;
end;
begin
  read(n);
  for i:=1 to n do
   begin
    read(m);
    m:=m-1;
    read(a1,b1,c,d);
    if (a1<>c)or(b1<>d) then begin q;end else writeln(0);
   end;
end.

C++(g++ 7.5.0) 解法, 执行用时: 136ms, 内存消耗: 548K, 提交时间: 2023-01-10 13:05:28

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
bool vis[333][333];
int ne[8][2]={-1,-2,-2,-1,1,2,2,1,1,-2,2,-1,-2,1,-1,2};
struct point{
	int x,y,step;
};
int bfs(int sx,int sy,int ex,int ey,int l)
{
	queue<point> q;
	q.push(point{sx,sy,0});
	vis[sx][sy]=true;
	while(q.size()>0)
	{
		point p=q.front();
		q.pop();
		for(int i=0;i<8;i++)
		{
			int dx=p.x+ne[i][0];
			int dy=p.y+ne[i][1];
			if((dx>=0&&dx<l&&dy>=0&&dy<l)&&vis[dx][dy]==false)
			{
				if(dx==ex&&dy==ey)
				{
					return p.step+1;
				}
				else
				{
					vis[dx][dy]=true;
					q.push(point{dx,dy,p.step+1});
				}
			}
		}
	}
	return 0;
}
int main()
{
	int n,l,sx,sy,ex,ey;
	cin>>n;
	while(n--)
	{
		memset(vis,0,sizeof(vis));
		cin>>l;
		cin>>sx>>sy>>ex>>ey;
		if(sx==ex&&sy==ey)
		{
			cout<<0<<endl;
			continue;
		}
		cout<<bfs(sx,sy,ex,ey,l)<<endl;
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 220ms, 内存消耗: 888K, 提交时间: 2019-10-28 11:33:24

#include<bits/stdc++.h>
using namespace std;
int dx[] = {1, -1, 1, -1, 2, -2, 2, -2};
int dy[] = {2, -2, -2, 2, 1, -1, -1, 1};


int main() {
  int n; cin >> n;
  while (n--) {
    int L; cin >> L;
    int sx, sy; cin >> sx >> sy;
    int tx, ty; cin >> tx >> ty;
    vector<vector<int>> steps(L, vector<int>(L, 0x3f3f3f3f));
    steps[sx][sy] = 0;
    queue<pair<int, int>> Q;
    Q.push({sx, sy});
    while (Q.size() && steps[tx][ty] == 0x3f3f3f3f) {
      int sx = Q.front().first; 
      int sy = Q.front().second; 
      Q.pop();
      for (int i = 0; i < 8; i++) {
        int tx = sx + dx[i];
        int ty = sy + dy[i];
        if (0 <= tx && tx < L && 0 <= ty && ty < L && steps[tx][ty]== 0x3f3f3f3f) {
          Q.push({tx, ty});
          steps[tx][ty] = steps[sx][sy] + 1;
        }
      }
    }
    cout << steps[tx][ty] << endl;
  }
}

C++(clang++ 11.0.1) 解法, 执行用时: 152ms, 内存消耗: 4352K, 提交时间: 2023-01-13 15:15:08

#include <bits/stdc++.h>
using namespace std;
const int N=1e3;
int L,sx,sy,ex,ey;
struct node{
	int x,y,step;
};
int book[N][N];
int dir[8][2] = {{2,-1},{2,1},{1,-2},{1,2},{-1,2},{-1,-2},{-2,-1},{-2,1}};
void bfs(){
	int step=0;
	queue<node>q;
	q.push({sx,sy,step});
	memset(book,0,sizeof(book));
	while(q.size()>0){
		node t=q.front();
		q.pop();
		if(t.x==ex&&t.y==ey){
			cout<<t.step<<endl;
			return;
		}
		
		for(int i=0;i<8;i++){
			int nx=t.x+dir[i][0];
			int ny=t.y+dir[i][1];
			if(nx>=0&&nx<L&&ny>=0&&ny<L&&book[nx][ny]==0){
				book[nx][ny]=1;
				q.push({nx,ny,t.step+1});
			}
		}
	}
}

int main(){
	int t;
	cin >> t;
	while(t--){
		cin>>L;
		cin >> sx >>sy>>ex>>ey;
		bfs();
	}
}