Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int N = 500, d[4][2]={{-1,0},{1,0},{0,-1},{0,1}}, INF = 1000000000;
int x[4], y[4], n, t[N][N], m;
bool vst[N][N];

int bfs(int u, int v) {
    if(vst[x[u]][y[u]]) return INF;
    vst[x[u]][y[u]] = true;
    queue<pair<int, int> > q;
    q.push(make_pair(x[u], y[u]));
    t[x[u]][y[u]] = -1;
    for(int step = 0; !q.empty(); ++step)
        for(int Z = (int) q.size(); Z > 0; --Z) {
            int a = q.front().first, b = q.front().second; q.pop();
            if(a == x[v] && b == y[v]) return step;
            for(int k = 0; k < 4; ++k) {
                int i = a + d[k][0], j = b + d[k][1];
                if(i >= 0 && i < m && j >= 0 && j < n && !vst[i][j]) {
                    vst[i][j] = true;
                    q.push(make_pair(i, j));
                    t[i][j] = k;
                }
            }
        }
    return INF;
}

int solve(int s, int f, int ss, int ff) {
    memset(vst, 0, sizeof vst);
    vst[x[ss]][y[ss]] = vst[x[ff]][y[ff]] = true;
    int res = bfs(s, f);
    if(res == INF) return INF;
    else {
        int u = x[f], v = y[f];
        memset(vst, 0, sizeof vst);
        for(int i = 0; i <= res; ++i) {
            vst[u][v] = true;
            int x = u - d[t[u][v]][0], y = v - d[t[u][v]][1];
            u = x; v = y;
        }
        res += bfs(ss, ff);
        if(res >= INF) return INF;
        return res;
    }
}

int main() {
    int tc; scanf("%d", &tc);
    while(tc--) {
        scanf("%d", &m); n = m;
        for(int i = 0; i < 4; ++i) scanf("%d", &x[i]);
        for(int i = 0; i < 4; ++i) scanf("%d", &y[i]);
        int res = solve(0, 1, 2, 3);
        res = min(res, solve(1, 0, 2, 3));
        res = min(res, solve(2, 3, 0, 1));
        res = min(res, solve(3, 2, 0, 1));
        if(res == INF) puts("-1");
        else printf("%d\n", res);
    }
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=501;
  di:array[1..4] of longint=(-1,1,0,0);
  dj:array[1..4] of longint=(0,0,-1,1);
type
  point=record x,y:longint; end;
var
  f1,f2:text;
  kq,n,first,last,test,t:longint;
  a1,a2,b1,b2:point;
  xet,tu,tv,dd:array[1..MAXN,1..MAXN] of longint;
  qd,qu,qv:array[1..MAXN*MAXN] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
begin
  read(f1,n);
  read(f1,a1.x,a2.x,b1.x,b2.x);
  read(f1,a1.y,a2.y,b1.y,b2.y);
  inc(a1.x); inc(a1.y);
  inc(a2.x); inc(a2.y);
  inc(b1.x); inc(b1.y);
  inc(b2.x); inc(b2.y);
end;
procedure ans;
begin
  if kq=maxlongint then writeln(f2,-1)
  else writeln(f2,kq);
end;
procedure swap(var a,b:point);
var
  temp:point;
begin
  temp:=a; a:=b; b:=temp;
end;
function bfs(targetu,targetv:longint):longint;
var
  u,v,uu,vv,d,h:longint;
begin
  while first<=last do
    begin
      u:=qu[first]; v:=qv[first]; d:=qd[first]; inc(first);
      if (u=targetu) and (v=targetv) then exit(d);
      for h:=1 to 4 do
        begin
          uu:=u+di[h]; vv:=v+dj[h];
          if (uu>0) and (vv>0) and (uu<=n) and (vv<=n) and (dd[uu,vv]=0) and (xet[uu,vv]=0) then
            begin
              tu[uu,vv]:=u; tv[uu,vv]:=v;
              xet[uu,vv]:=1;
              inc(last); qu[last]:=uu; qv[last]:=vv; qd[last]:=d+1;
            end;
        end;
    end;
  exit(-1);
end;
procedure trace(targetu,targetv,startu,startv:longint);
var
  u,v,uu,vv:longint;
begin
  u:=targetu; v:=targetv;
  while (u<>startu) or (v<>startv) do
    begin
      dd[u,v]:=1;
      uu:=tu[u,v]; vv:=tv[u,v];
      u:=uu; v:=vv;
    end;
end;
procedure solve;
var
  u,v,uu,vv,h,x,y:longint;
begin
  fillchar(dd,sizeof(dd),0);
  fillchar(xet,sizeof(xet),0);
  dd[a1.x,a1.y]:=1;
  dd[b1.x,b1.y]:=1;
  dd[b2.x,b2.y]:=1;
  first:=1; last:=1; qu[1]:=a1.x; qv[1]:=a1.y; qd[1]:=0;
  xet[a1.x,a1.y]:=1;
  x:=bfs(a2.x,a2.y);
  if x=-1 then exit;
  trace(a2.x,a2.y,a1.x,a1.y);
  fillchar(xet,sizeof(xet),0);
  first:=1; last:=1; qu[1]:=b1.x; qv[1]:=b1.y; qd[1]:=0;
  xet[b1.x,b1.y]:=1;
  dd[b2.x,b2.y]:=0;
  dd[a2.x,a2.y]:=1;
  y:=bfs(b2.x,b2.y);
  if y=-1 then exit;
  kq:=min(kq,x+y);
end;
begin
  openF;
  read(f1,t);
  for test:=1 to t do
    begin
      inp;
      if ((a1.x=b1.x) and (a1.y=b1.y))
      or ((a1.x=b2.x) and (a1.y=b2.y))
      or ((a2.x=b1.x) and (a2.y=b1.y))
      or ((a2.x=b2.x) and (a2.y=b2.y)) then
        begin
          writeln(f2,-1);
          continue;
        end;
      kq:=maxlongint;
      solve;
      swap(a1,b1); swap(a2,b2);
      solve;
      ans;
    end;
  closeF;
end.

Code mẫu của skyvn97

#include<cstdio>
#include<queue>
#define MAX   505
#define INF   1e9
#define x   first
#define y   second
using namespace std;
typedef pair<int,int> ii;
int c[MAX][MAX];
int l[MAX][MAX];
ii a1,a2,b1,b2,c1,c2;
int m,n;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
void swap(ii &a,ii &b) {
    ii sw;
    sw=a;a=b;b=sw;
}
int abs(int x) {
    if (x<0) return (-x); else return (x);
}
void process(void);
void init(void) {
    scanf("%d",&n);
    n=n-1;
    m=n;
    scanf("%d",&a1.x);
    scanf("%d",&a2.x);
    scanf("%d",&b1.x);
    scanf("%d",&b2.x);
    scanf("%d",&a1.y);
    scanf("%d",&a2.y);
    scanf("%d",&b1.y);
    scanf("%d",&b2.y);
    if (a1.x==a2.x && a2.x==b1.x && b1.x==b2.x) {
        if (a1.y>a2.y) swap(a1,a2);
        if (b1.y>b2.y) swap(b1,b2);
        if (a1.y>b1.y) {
            swap(a1,b1);
            swap(a2,b2);
        }
        if (a2.y<b1.y) {
            printf("%d\n",a2.y-a1.y+b2.y-b1.y);
            return;
        }
        if (a2.y<b2.y) {
            if (a1.x*(a1.x-m)==0) printf("-1\n");
            else printf("%d\n",a2.y-a1.y+b2.y-b1.y+4);
            return;
        }
        printf("%d\n",a2.y-a1.y+b2.y-b1.y+2);
        return;
    }
    if (a1.y==a2.y && a2.y==b1.y && b1.y==b2.y) {
        if (a1.x>a2.x) swap(a1,a2);
        if (b1.x>b2.x) swap(b1,b2);
        if (a1.x>b1.x) {
            swap(a1,b1);
            swap(a2,b2);
        }
        if (a2.x<b1.x) {
            printf("%d\n",a2.x-a1.x+b2.x-b1.x);
            return;
        }
        if (a2.x<b2.x) {
            if (a1.y*(a1.y-n)==0) printf("-1\n");
            else printf("%d\n",a2.x-a1.x+b2.x-b1.x+4);
            return;
        }
        printf("%d\n",a2.x-a1.x+b2.x-b1.x+2);
        return;
    }
    c1=ii(b1.x,b2.y);
    c2=ii(b2.x,b1.y);
    if (c1==a1 && c2==a2) {
        if (abs(b1.x-b2.x)+abs(b1.y-b2.y)<3) {
            printf("-1\n");
            return;
        }
        if (a1.x==b1.x && abs(a1.y-b1.y)==n) {
            printf("-1\n");
            return;
        }
        if (a1.y==b1.y && abs(a1.x-b1.x)==m) {
            printf("-1\n");
            return;
        }
        if (a1.x==b2.x && abs(a1.y-b2.y)==n) {
            printf("-1\n");
            return;
        }
        if (a1.y==b2.y && abs(a1.x-b2.x)==m) {
            printf("-1\n");
            return;
        }
        printf("%d\n",2*(abs(b1.x-b2.x)+abs(b1.y-b2.y))+4);
        return;
    }
    process();
}
int min(int x,int y) {
    if (x<y) return (x); else return (y);
}
int max(int x,int y) {
    if (x>y) return (x); else return (y);
}
bool test(int x,int y) {
    if (x<0) return (false);
    if (y<0) return (false);
    if (x>m) return (false);
    if (y>n) return (false);
    return (c[x][y]==0);
}
int BFS(ii A,ii B,ii C,ii D,ii E) {
    int i,j,r;
    r=-2;
    for (i=0;i<=m;i=i+1)
        for (j=0;j<=n;j=j+1) {
            c[i][j]=0;
            l[i][j]=0;
        }
    if (A.x==B.x) {
        for (j=min(A.y,B.y);j<=max(A.y,B.y);j=j+1) {
            c[A.x][j]=1;
            r=r+1;
        }
    }
    else  {
        for (j=min(A.x,B.x);j<=max(A.x,B.x);j=j+1) {
            c[j][A.y]=1;
            r=r+1;
        }
    }
    if (B.x==C.x) {
        for (j=min(B.y,C.y);j<=max(B.y,C.y);j=j+1) {
            c[B.x][j]=1;
            r=r+1;
        }
    }
    else  {
        for (j=min(B.x,C.x);j<=max(B.x,C.x);j=j+1) {
            c[j][B.y]=1;
            r=r+1;
        }
    }
    if (c[D.x][D.y]>0) return (INF);
    if (c[E.x][E.y]>0) return (INF);
    queue<ii> q=queue<ii>();
    q.push(D);
    c[D.x][D.y]=1;
    ii p;
    int px,py;
    while (!q.empty()) {
        p=q.front();q.pop();
        px=p.x;py=p.y;
        for (i=0;i<4;i=i+1)
            if (test(px+dx[i],py+dy[i])) {
                c[px+dx[i]][py+dy[i]]=1;
                l[px+dx[i]][py+dy[i]]=l[px][py]+1;
                q.push(ii(px+dx[i],py+dy[i]));
            }
    }
    if (c[E.x][E.y]==0) return (INF);
    return (l[E.x][E.y]+r);
}
int BFS2(ii A,ii B,ii C,ii D,ii E,ii F) {
    int i,j;
    int r=-3;
    for (i=0;i<=m;i=i+1)
        for (j=0;j<=n;j=j+1) {
            c[i][j]=0;
            l[i][j]=0;
        }
    if (A.x==B.x) {
        for (i=min(A.y,B.y);i<=max(A.y,B.y);i=i+1) {
            c[A.x][i]=1;
            r=r+1;
        }
    }
    else {
        for (i=min(A.x,B.x);i<=max(A.x,B.x);i=i+1) {
            c[i][A.y]=1;
            r=r+1;
        }
    }
    if (B.x==C.x) {
        for (i=min(B.y,C.y);i<=max(B.y,C.y);i=i+1) {
            c[B.x][i]=1;
            r=r+1;
        }
    }
    else {
        for (i=min(B.x,C.x);i<=max(B.x,C.x);i=i+1) {
            c[i][B.y]=1;
            r=r+1;
        }
    }
    if (C.x==D.x) {
        for (i=min(C.y,D.y);i<=max(C.y,D.y);i=i+1) {
            c[C.x][i]=1;
            r=r+1;
        }
    }
    else {
        for (i=min(C.x,D.x);i<=max(C.x,D.x);i=i+1) {
            c[i][C.y]=1;
            r=r+1;
        }
    }
    if (c[E.x][E.y]>0) return (INF);
    if (c[F.x][F.y]>0) return (INF);
    queue<ii> q=queue<ii>();
    q.push(E);
    c[E.x][E.y]=1;
    ii p;
    int px,py;
    while (!q.empty()) {
        p=q.front();q.pop();
        px=p.x;py=p.y;
        for (i=0;i<4;i=i+1)
            if (test(px+dx[i],py+dy[i])) {
                c[px+dx[i]][py+dy[i]]=1;
                l[px+dx[i]][py+dy[i]]=l[px][py]+1;
                q.push(ii(px+dx[i],py+dy[i]));
            }
    }
    if (c[F.x][F.y]==0) return (INF);
    return (l[F.x][F.y]+r);
}
void process(void) {
    ii p,q;
    int res=INF;
    p=ii(a1.x,a2.y);
    res=min(res,BFS(a1,p,a2,b1,b2));
    p=ii(a2.x,a1.y);
    res=min(res,BFS(a1,p,a2,b1,b2));
    p=ii(b1.x,b2.y);
    res=min(res,BFS(b1,p,b2,a1,a2));
    p=ii(b2.x,b1.y);
    res=min(res,BFS(b1,p,b2,a1,a2));
    if (a1.x<a2.x) {
        p=ii(a1.x+1,a1.y);
        q=ii(a1.x+1,a2.y);
        res=min(res,BFS2(a1,p,q,a2,b1,b2));
        p=ii(a2.x-1,a1.y);
        q=ii(a2.x-1,a2.y);
        res=min(res,BFS2(a1,p,q,a2,b1,b2));
    }
    if (a1.y<a2.y) {
        p=ii(a1.x,a1.y+1);
        q=ii(a2.x,a1.y+1);
        res=min(res,BFS2(a1,p,q,a2,b1,b2));
        p=ii(a1.x,a2.y-1);
        q=ii(a2.x,a2.y-1);
        res=min(res,BFS2(a1,p,q,a2,b1,b2));
    }
    if (b1.x<b2.x) {
        p=ii(b1.x+1,b1.y);
        q=ii(b1.x+1,b2.y);
        res=min(res,BFS2(b1,p,q,b2,a1,a2));
        p=ii(b2.x-1,b1.y);
        q=ii(b2.x-1,b2.y);
        res=min(res,BFS2(b1,p,q,b2,a1,a2));
    }
    if (b1.y<b2.y) {
        p=ii(b1.x,b1.y+1);
        q=ii(b2.x,b1.y+1);
        res=min(res,BFS2(b1,p,q,b2,a1,a2));
        p=ii(b1.x,b2.y-1);
        q=ii(b2.x,b2.y-1);
        res=min(res,BFS2(b1,p,q,b2,a1,a2));
    }

    if (a2.x<a1.x) {
        p=ii(a2.x+1,a1.y);
        q=ii(a2.x+1,a2.y);
        res=min(res,BFS2(a1,p,q,a2,b1,b2));
        p=ii(a1.x-1,a1.y);
        q=ii(a1.x-1,a2.y);
        res=min(res,BFS2(a1,p,q,a2,b1,b2));
    }
    if (a2.y<a1.y) {
        p=ii(a1.x,a2.y+1);
        q=ii(a2.x,a2.y+1);
        res=min(res,BFS2(a1,p,q,a2,b1,b2));
        p=ii(a1.x,a1.y-1);
        q=ii(a2.x,a1.y-1);
        res=min(res,BFS2(a1,p,q,a2,b1,b2));
    }
    if (b2.x<b1.x) {
        p=ii(b2.x+1,b1.y);
        q=ii(b2.x+1,b2.y);
        res=min(res,BFS2(b1,p,q,b2,a1,a2));
        p=ii(b1.x-1,b1.y);
        q=ii(b1.x-1,b2.y);
        res=min(res,BFS2(b1,p,q,b2,a1,a2));
    }
    if (b2.y<b1.y) {
        p=ii(b1.x,b2.y+1);
        q=ii(b2.x,b2.y+1);
        res=min(res,BFS2(b1,p,q,b2,a1,a2));
        p=ii(b1.x,b1.y-1);
        q=ii(b2.x,b1.y-1);
        res=min(res,BFS2(b1,p,q,b2,a1,a2));
    }
    if (res>=INF) printf("-1\n");
    else printf("%d\n",res);
}
int main(void) {
    int t,c;
    scanf("%d",&t);
    for (c=1;c<=t;c=c+1) init();
    return 0;
}