{ File: lab2.pas } program ProgrammaLabirinto2; { Questa volta le costanti significative del programma sono poste in questo file, in modo da renderle piu' facilmente modificabili. } const N = 10; M = 15; PASSAGGIO = '-'; { carattere che indica un punto di passaggio nel labirinto } EVIDENTE = ' '; { carattere che evidenzia un punto di passaggio nel percorso attraverso il labirinto } { Ora includiamo il file con le definizioni. Si tratta di un file piu' esteso di LABIRINT.DEF, con definizioni anche per il tipo ATTRAVERSAMENTO e di due procedure per la stampa di una variabile di tipo ATTRAVERSAMENTO e per il riversamento in una matrice LABIRINTO di un attraversamento. } {$I LABDEF2.PAS} var riga, i : INDICERIGA; { per scandire le righe del labirinto } colonna, j : INDICECOLONNA; { per scandire le colonne del labirinto } filedat : text; { filedati per il labirinto } labirint : LABIRINTO; { matrice labirinto } percorso : ATTRAVERSAMENTO; { vettore per il percorso } trovato : boolean; { =TRUE se si e' trovato un percorso } procedure VisitaLabirinto (lab: labirinto; r: INDICERIGA; c: INDICECOLONNA; var trovato: boolean; var att: ATTRAVERSAMENTO); { Visita il labirinto lab a partire dal punto di entrata (r,c) e memorizza il percorso trovato (se trovato) nell'array att. Il parametro "trovato" viene assegnato a TRUE/FALSE se e' stato trovato/non-trovato un percorso effettivo. 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 li') e assegna il parametro Trovato di VisitaLabirinto opportunamente } var k1, k2 : integer; marcheLabirinto : array [INDICERIGA, INDICECOLONNA] of boolean; procedure RicercaCammino (i: indiceriga; j: indicecolonna; var trovato: boolean; ultimocamm: TNcamm); { Usa le variabili non locali: - lab (parametro di VisitaLabirinto) - trovato (parametro di VisitaLabirinto) - marchelabirinto (variabile locale di VisitaLabirinto) - att (parametro di VisitaLabirinto) 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 } att[ultimocamm].coordi := i; att[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 sara` un punto esistente e di passaggio e non ancora visitato, andra` aggiunto nel cammino nella posizione successiva. Immaginiamo non sia ammesso muoversi in diagonale (per permetterlo basta de-commentare le chiamate poste in commento). Notare che modificando l'ordine delle chiamate si possono organizzare delle vere e proprie strategie di ricerca (ad esempio, usando la matrice labirint.dat, la procedura attuale trova un percorso uscente a destra del labirinto. Questo perche` nelle chiamate di RicercaCammino si da` la precedenza agli spostamenti verso destra e poi agli altri; invertendo l'ordine delle prime due chiamate qui sotto, la procedura trova un percorso diverso). } 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; { Inizio ricerca cammino dal punto di entrata inserire in cammino[1] il nuovo elemento del cammino } RicercaCammino(r, c, trovato, 1); end; { VisitaLabirinto } begin { ProgrammaLabirinto2 } assign(filedat, 'a:labirint.dat'); Leggilabirinto(filedat, labirint); stampalabirinto(labirint); writeln; writeln('punto di entrata ?'); readln(riga, colonna); writeln; { attraversamento ancora non trovato } trovato := FALSE; VisitaLabirinto(labirint, riga, colonna, trovato, percorso); if trovato then begin StampaAttraversamento(percorso, 4); StampaPercorsoSuLabirinto(labirint, percorso) end else writeln('nessun cammino trovato') end. { ProgrammaLabirinto2 }