Поиск пути в лабиринте

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. 
 
[ATTACH]764226[/ATTACH]