Editorial for Mã và tốt


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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 RR

//Written by Nguyen Thanh Trung
{$IFDEF RR}
  {$R+,Q+}
  {$Mode objFPC}
  {$inline off}
{$ELSE}
  {$R-,Q-}
  {$inline on}
{$ENDIF}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       1020;
  di            :       array[1..8] of longint=(-1,-1,0,0,2,2,3,3);
  dj            :       array[1..8] of longint=(-1,1,-2,2,-2,2,-1,1);
type
  Tqueue        =       object
        u,v     :       array[1..MAXN*MAXN*4] of longint;
        first   :       longint;
        last    :       longint;
        procedure push(uu,vv,d:longint);
        procedure pop(var uu,vv:longint);
  end;
var
  f1,f2         :       text;
  mx,my,tx,ty   :       longint;
  first         :       longint;
  m,n           :       longint;
  dd            :       array[-MAXN..MAXN,-MAXN..MAXN] of longint;
  queue         :       Tqueue;

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,mx,my);
      read(f1,tx,ty);
      read(f1,first);
      m:=max(mx,tx)+10;
      n:=max(my,ty)+10;
    end;
procedure Tqueue.push(uu,vv,d:longint); inline;
    begin
      if (uu<-1010) or (vv<-1010) or (uu>1010) or (vv>1010) then exit;
      if (dd[uu,vv]>0) then exit;
      dd[uu,vv]:=d;
      inc(last);
      u[last]:=uu;
      v[last]:=vv;
    end;
procedure Tqueue.pop(var uu,vv:longint); inline;
    begin
      uu:=u[first];
      vv:=v[first];
      inc(first);
    end;
procedure init;
    begin
      queue.first:=1; queue.last:=0;
      if first=1 then queue.push(mx,my,1)
      else
        begin
          queue.push(mx-2,my-1,2);
          queue.push(mx-2,my+1,2);
          queue.push(mx-1,my-2,2);
          queue.push(mx-1,my+2,2);
          queue.push(mx+1,my-2,2);
          queue.push(mx+1,my+2,2);
          queue.push(mx+2,my-1,2);
          queue.push(mx+2,my+1,2);
        end;
    end;
procedure solve;
    var
      d,u,v,uu,vv,dir,i:longint;
    begin
      while queue.first<=queue.last do
        begin
          queue.pop(u,v); d:=dd[u,v];
          for dir:=1 to 8 do
            begin
              uu:=u+di[dir]; vv:=v+dj[dir];
              if dd[uu,vv]>0 then continue;
              if (uu=tx) and (vv=ty) then
                begin
                  writeln(f2,'YES');
                  writeln(f2,d);
                  exit;
                end;
              queue.push(uu,vv,d+1);
            end; //for dir
        end; //while queue.first<=queue.last
      writeln(f2,'NO');
    end;

begin
  openF;
  inp;
  init;
  solve;
  closeF;
end.

Code mẫu của ll931110

Program KANDP2;
Const
  input  = '';
  output = '';
  dx: array[1..8] of integer = (2,1,-1,-2,-2,-1,1,2);
  dy: array[1..8] of integer = (1,2,2,1,-1,-2,-2,-1);
  maxn = 1003;
Type
  rec = record
    x,y: integer;
  end;

  PNode = ^TNode;
  TNode = record
    val: rec;
    link: PNode;
  end;
Var
  d: array[-maxn..maxn,-maxn..maxn] of integer;
  front,rear: PNode;
  mx,my,tx,ty,k: integer;

Procedure init;
Var
  f: text;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, mx, my);
  Readln(f, tx, ty);

  Readln(f, k);
  Close(f);
End;

Procedure push(v: rec);
Var
  P: PNode;
Begin
  New(P);
  P^.val:= v;
  P^.link:= nil;
  If front = nil then Front:= P else Rear^.link:= P;
  Rear:= P;
End;

Function pop: rec;
Var
  P: PNode;
Begin
  pop:= Front^.val;
  P:= Front^.link;
  Dispose(front);
  Front:= P;
End;

Procedure BFS;
Var
  i: integer;
  u,v: rec;
Begin
  Fillchar(d, sizeof(d), 0);
  front:= nil;

  u.x:= mx;
  u.y:= my;
  push(u);

  If k = 0 then
    Begin
      u:= pop;
      For i:= 1 to 8 do
        Begin
          v.x:= u.x + dx[i];
          v.y:= u.y + dy[i];

          If ((abs(v.x) <= maxn) and (abs(v.y) <= maxn)) then
            Begin
              d[v.x,v.y]:= 1;
              If (v.x = tx) and (v.y = ty) then exit;
              push(v);
            End;
        End;
    End;

  Repeat
    u:= pop;
    For i:= 1 to 8 do
      Begin
        v.x:= u.x + dx[i] + 1;
        v.y:= u.y + dy[i];

        If (abs(v.x) <= maxn) and (abs(v.y) <= maxn) and (d[v.x,v.y] = 0) then
          Begin
            d[v.x,v.y]:= d[u.x,u.y] + 1;
            If (v.x = tx) and (v.y = ty) then exit;
            push(v);
          End;
      End;
  Until front = nil;
End;

Procedure printresult;
Var
  f: text;
Begin
  Assign(f, output);
    Rewrite(f);
    If d[tx,ty] = 0 then writeln(f, 'NO') else
      Begin
        Writeln(f, 'YES');
        Writeln(f, d[tx,ty]);
      End;
  Close(f);
End;

Begin
  init;
  BFS;
  printresult;
End.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.