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
|
program LABYRINTH; {BACKTRACK1, i.e. depth-first, no infinite cycle}
const M = 7; N = 7; {Dimensions}
var LAB : array[1..M, 1..N] of integer; {Labyrinth}
CX, CY : array[1..4] of integer; {4 production – shifts in X and Y}
L, {Move’s number. Starts from 2. Visited positions are marked}
X, Y, {Agent’s initial position}
I, J, {Loop variables}
TRIAL : integer; {Number of trials. To compare effectiveness}
YES : boolean; {true – success, false - failure}
procedure TRY(X, Y : integer; var YES : boolean);
var K, {The number of a production rule}
U, V : integer; {Agent’s new position}
begin {TRY}
if (X = 1) or (X = M) or (Y = 1) or (Y = N)
then YES := true {TERM(DATA} = true on the boarder}
else
begin K := 0;
repeat K := K + 1; {Next rule. Loop over production rules}
U := X + CX[K]; V := Y + CY[K]; {Agent’s new position }
if LAB[U, V] = 0 {If a cell is free}
then
begin TRIAL := TRIAL + 1; {Number of trials}
L := L + 1; LAB[U,V] := L;{Marking the cell}
TRY(U, V, YES); {Recursive call}
if not YES {If failure}
then begin {K8}
LAB[U,V] := -1; {then mark. (0 in case of BACKTRACK)}
L := L - 1;
end;
end;
until YES or (K = 4);
end;
end; {TRY}
begin {main program} {1. Reading the labyrinth}
for J := N downto 1 do
begin
for I := 1 to M do read(LAB[I,J]);
readln;
end;
{2. Reading agent’s position}
read(X, Y); L := 2; LAB[X,Y] := L;
{3. Forming four production rules}
CX[1] := -1; CY[1] := 0; {Go West. 4 }
CX[2] := 0; CY[2] := -1; {Go South. 1 * 3 }
CX[3] := 1; CY[3] := 0; {Go East. 2 }
CX[4] := 0; CY[4] := 1; {Go North. }
{4. Initialising variables}
YES := false; TRIAL := 0;
{5. Invoking the BACKTRACK1 procedure}
TRY(X, Y, YES);
if YES
then writeln('Path exists'); {Please also print the path found.}
else writeln('Path does not exist'); {No paths exist.}
end.
|