Hướng dẫn giải của Mã và tốt
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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.
Bình luận