1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
program LABYRINTH_BREADTH_FIRST (input, output);
const
M = 7; N = 7; {The dimensions of the labyrinth.}
MN = 49; {The number of cells M*N. }
var
LAB, LABCOPY : array[1..M, 1..N] of integer; {Labyrinth and its copy.}
CX, CY : array[1..4] of integer; {4 production rules.}
FX, FY : array[1..MN] of integer; {The “front” to store opened nodes.}
CLOSE, {The counter for a closed node.}
NEWN, {The counter for an opened node.}
K, {The counter for a production.}
X, Y, {The starting position of the agent.}
U, V, I, J : integer;
YES : boolean;
procedure BACK(U, V : integer); {Collect the path from the exit to start.}
{INPUT: 1) U, V – the coordinates of the exit, and 2) global LABCOPY.
OUTPUT: LAB.}
var K, UU, VV : integer;
begin {BACK}
LAB[U,V] := LABCOPY[U,V]; {The exit position is marked.}
K := 0;
repeat {The search within 4 productions. Search for cell LABCOPY[UU,VV]
with the mark which is 1 less than LABCOPY[U,V].}
K := K + 1; UU := U + CX[K]; VV := V + CY[K];
if (1 <= UU) and (UU <= M) and (1 <= VV) and (VV <= N)
then {Inside the boarders}
if LABCOPY[UU,VV] = LABCOPY[U,V] – 1
then
begin
LAB[UU,VV] := LABCOPY[UU,VV] ; {Marking a cell in LAB.}
U := UU; V := VV; K := 0; {Swapping the variables.}
end;
until LABCOPY[U, V] = 2;
end; {BACK}
begin {Main program}
{ 1) Reading the labyrinth.}
for J := N downto 1 do
begin
for I := 1 to M do
begin read(LAB[I,J]);
LABCOPY[I,J]:= LAB[I,J];
end
readln;
end;
{ 2) Reading the starting position of the agent.}
read(X,Y); LABCOPY[X,Y]:=2;
{ 3) Initialising 4 production rules}
CX[1] := -1; CY[1] := 0; {Go West. 2 }
CX[2] := 0; CY[2] := -1; {Go South. 1 * 3 }
CX[3] := 1; CY[3] := 0; {Go East. 4 }
CX[4] := 0; CY[4] := 1; {Go North. }
{ 4) Assigning initial values.}
FX[1] := X; FY[1] := Y; CLOSE := 1; NEWN := 1; YES := false;
{ 5) Breadth-first search, i.e. the “wave” algorithm.}
if (X = 1) or (X = M) or (Y = 1) or (Y = N)
then {If an exit is reached then finish.}
begin YES := true; U := X; V := Y;
end;
if (X > 1) and (X < M) and (Y > 1) and (Y < N)
then
repeat {The loop through the nodes.}
X := FX[CLOSE]; Y := FY[CLOSE]; {Coordinates of node to be closed.}
K := 0;
repeat {The loop trough 4 production rules.}
K := K + 1; U := X + CX[K]; V := Y + CY[K];
if LABCOPY[U, V] = 0 {The cell is free.}
then begin
LABCOPY[U,V] := LABCOPY[X,Y] + 1; {New wave’s number.}
if (U = 1) or (U = M) or (V = 1) or (V = N) {Boarder.}
then YES := true; {Success. Here BACK(U,V) could be called.}
else begin {Placing a newly opened node into front’s end.}
NEWN := NEWN + 1; FX[NEWN] := U; FY[NEWN] := V;
end;
end;
until (K = 4) or YES; {Each of 4 productions is checked or success.}
CLOSE := CLOSE + 1; {Next node will be closed.}
until (CLOSE > NEWN) or YES;
{ 6) Printing the path found.}
if YES
then begin
writeln('A path exists.');
BACK(U,V); {Collecting the path.}
{ Here a procedure should be called to print the path.}
end
else writeln('A path does not exist.');
end.
|
