PHP Code:
Uses Crt;
Const
Dx : array***91;1..4***93; of Integer = (-1,0,0,1);
Dy : array***91;1..4***93; of Integer = (0,-1,1,0);
Max = 50;
Type
O = Record
Row, Col : Integer;
End;
Var
Matrix:Array***91;1..Max,1..Max***93; of Char;
Queue:Array***91;1..Max***93; of O;
Trace:Array***91;1..Max,1..Max***93; of O;
m,n,First,Last:Integer;
xp:O;
Procedure Enter;
Var i,j:Integer;
F:Text;
Begin
Assign(F,'mecung.inp'); Reset(F);
Readln(F,m,n);
For i:=1 to m do
Begin
For j:=1 to n do
Begin
Read(F,Matrix***91;i,j***93;);
If Matrix***91;i,j***93;='e' then
Begin
Xp.Row:=i;
Xp.Col:=j;
End;
End;
Readln(F);
End;
Close(F);
End;
Function Done(i,j:Integer):Boolean;
Begin
If ((i=1) or (i=m) or (j=1) or (j=n))
And (Matrix***91;i,j***93;='o') then Done:=True
Else Done:=False;
End;
Function InTable(i,j:Integer):Boolean;
Begin
If (1<=i) and (i<=m) and (1<=j) and (j<=n) then
InTable:=True
Else InTable:=False;
End;
Procedure Push(v:O);
Begin
Inc(Last); Queue***91;Last***93;:=v;
End;
Function Pop:O;
Begin
Pop:=Queue***91;First***93;; Inc(First);
End;
Procedure BFS;
Var
i,j,k:Integer;
u,v:O;
Begin
Queue***91;1***93;:=xp;
First:=1; Last:=1;
Repeat
u:=Pop;
For i:=1 to 4 do
Begin
v.Row:=u.Row+Dx***91;i***93;;
v.Col:=u.Col+Dy***91;i***93;;
If (InTable(v.Row,v.Col)) and (Matrix***91;v.Row,v.Col***93;='o') then
Begin
Push(v);
Trace***91;u.Row,u.Col***93;:=v;
End;
End;
Until Done(v.Row,v.Col);
End;
Procedure PrintResult;
Var v:O;
Begin
v:=xp;
Repeat
Begin
Write('(',v.Row,',',v.Col,')->');
v:=Trace***91;v.Row,v.Col***93;;
End;
Until Done(v.Row,v.Col);
If Done(v.Row,v.Col) then
Begin
Write('(',v.Row,',',v.Col,')');
End;
End;
BEGIN
ClrScr;
Enter;
BFS;
PrintResult;
Readln;
END.
Khác với mấy bài cơ bản là trace ngược thì bài này trace xuôi.
Bookmarks