{ File: labirint.pas } program ProgrammaLabirinto; { Inclusione delle definizioni di labirinto } {$I LABIRDEF.PAS} var riga, i : IndiceRiga; colonna, j : IndiceColonna; filedat : text; labirint : Labirinto; procedure VisitaLabirinto (lab: Labirinto; r: IndiceRiga; c: IndiceColonna); { Visita il labirinto a partire dal punto di entrata r,c. Una uscita e` un punto di passaggio con coordinata i=1 o i=n o j=1 o j=m, che sia diverso da r,c. La procedura controlla se il punto di entrata e` effettivamente di passaggio e poi procede lanciando la RicercaCammino su ogni punto adiacente che sia di passaggio. RicercaCammino marca il punto da cui sta partendo nella matrice marcheLabirinto (per evitare di far ripartire ricerche da l) e assegna il parametro Trovato di VisitaLabirinto opportunamente. Per memorizzare il cammino di attraversamento non possiamo che far uso di un vettore. Lo chiamiamo "cammino" e lo dimensioniamo in modo che possa contenere qualunque cammino possibile: il cammino piu` lungo per uscire da un labirinto avente solo i muri perimetrali - con 1 entrata e una uscita - e niente all'interno, e' nm-2m-2n+6. } const NCAMM = n * m - 2 * m - 2 * n + 6; type TNcamm = 1..NCAMM; var k1, k2 : integer; marcheLabirinto : array [IndiceRiga, IndiceColonna] of boolean; trovato : boolean; cammino : array [TNcamm] of record coordi : IndiceRiga; coordj : IndiceColonna; end; { variabile di tipo molto "ad hoc" per contenere il cammino ciascun elemento rappresenta un punto del cammino percorso. Il cammino termina con successo quando contiene un punto di passaggio con coordi=N o 1 oppure coordj=M o 1. Gli elementi successivi del cammino verranno ignorati da una eventuale stampa. } procedure RicercaCammino (i: IndiceRiga; j: IndiceColonna; var trovato: boolean; ultimocamm: TNcamm); { usa le variabili non locali: - lab (parametro di VisitaLabirinto) - trovato (var locale di VisitaLabirinto) - marchelabirinto (") - cammino (") il parametro ultimocamm dice in quale componente di cammino va memorizzato il nuovo elemento i,j. Le prossime aggiunte lungo il cammino andranno fatte da ultimocamm+1 in poi. } begin { RicercaCammino } { writeln(' ricerca ', i : 2, j : 2); } if (i >= 1) and (i <= N) and (j > 0) and (j <= M) then { Il punto esiste. Se e' gia' stato visitato o non e' di passaggio, non bisogna fare nulla. Se e' un punto di passaggio non ancora visitato, allora bisogna inserirlo nel cammino e attivare la ricerca sui punti adiacenti. } if not (marchelabirinto[i, j]) and (lab[i, j] = PASSAGGIO) then begin { *** } { inserisce il punto nel cammino } cammino[ultimocamm].coordi := i; cammino[ultimocamm].coordj := j; { marca questo punto del labirinto } marchelabirinto[i, j] := TRUE; { determina se il punto e' conclusivo } if (i = 1) or (i = N) or (j = 1) or (j = M) then if not ((i = r) and (j = c)) then { non e' il punto di entrata: va bene } trovato := TRUE; { se non e' trovato=true bisogna cercare il cammino a partire da uno dei punti intorno a quello attuale. Il nuovo punto del cammino - se sarˆ un punto esistente e di passaggio e non ancora visitato, andra` aggiunto nel cammino nella posizione successiva. Immaginiamo non sia ammesso muoversi in diagonale (chiamate poste in commento). Notare che modificando l'ordine delle chiamate si possono organizzare delle vere e proprie strategie di ricerca del percorso (prima a destra poi in alto oppure prima in alto e poi a destra ... etc...). } if not trovato then RicercaCammino(i, j + 1, trovato, ultimocamm + 1); { if not trovato then RicercaCammino(i - 1, j + 1, trovato, ultimocamm + 1); } { if not trovato then RicercaCammino ( i + 1 , j + 1 , trovato , ultimocamm + 1 ); } if not trovato then RicercaCammino(i + 1, j, trovato, ultimocamm + 1); if not trovato then RicercaCammino(i - 1, j, trovato, ultimocamm + 1); if not trovato then RicercaCammino(i, j - 1, trovato, ultimocamm + 1); { if not trovato then RicercaCammino ( i - 1 , j - 1 , trovato , ultimocamm + 1 ); } { if not trovato then RicercaCammino(i + 1, j - 1, trovato, ultimocamm + 1); } end { *** } end; { RicercaCammino } begin { VisitaLabirinto } { Init marchelabirinto: FALSE = "il punto non e` stato visitato. I punti visitati verranno marcati con TRUE da RicercaCammino. } for k1 := 1 to N do for k2 := 1 to M do marcheLabirinto[k1, k2] := FALSE; { attraversamento ancora non trovato } trovato := FALSE; { Inizio ricerca cammino dal punto di entrata. Inserire in cammino[1] il nuovo elemento del cammino. } RicercaCammino(r, c, trovato, 1); if trovato then begin writeln('cammino trovato ...'); write('(', cammino[1].coordi, ',', cammino[1].coordj, ') '); k1 := 1; repeat k1 := k1 + 1; write('(', cammino[k1].coordi, ',', cammino[k1].coordj, ') '); until (cammino[k1].coordi = 1) or (cammino[k1].coordj = 1) or (cammino[k1].coordi = N) or (cammino[k1].coordj = M); writeln; end else writeln('nessun cammino trovato'); end; { VisitaLabirinto } begin { ProgrammaLabirinto } assign(filedat, 'a:labirint.dat'); Leggilabirinto(filedat, labirint); stampalabirinto(labirint); writeln; writeln('punto di entrata ?'); readln(riga, colonna); writeln; VisitaLabirinto(labirint, riga, colonna); writeln('fine'); readln end. { ProgrammaLabirinto }