{ File: palude3.pas } { Scopo: esercizio significativo sull'uso di pile } program AttraversaPalude; { Legge da un file di testo una matrice di 0 e 1 che rappresenta una palude, la stampa, cerca un attraversamento e lo stampa se esiste. Variante in cui sono possibili movimenti solo in avanti, cioe` da <riga,colonna> a - <riga-1, colonna+1> (solo se la riga non e` la prima) - <riga, colonna+1> - <riga+1, colonna+1> (solo se la riga non e` l'ultima) Soluzione che fa uso di una pila in modo analogo alla pila usata per visitare un grafo. } const R = 5; { numero di righe, cioe` larghezza della palude } C = 7; { numero di colonne, cioe` lunghezza della palude, coincide con la lunghezza di un cammino attraverso la palude } type TipoRiga = 1..R; TipoColonna = 1..C; TipoPalude = array [TipoRiga, TipoColonna] of 0..1; TipoCammino = array [TipoColonna] of TipoRiga; TipoPosizione = record riga : TipoRiga; colonna : TipoColonna end; TipoElemPila = TipoPosizione; { gli elementi della pila sono posizioni nella palude } {$I PILE.PAS} { Inclusione delle procedure e funzioni per la gestione di pile } procedure SvuotaPila (var p : TipoPila); { Svuota la pila p. } var e : TipoElemPila; begin while not TestPilaVuota(p) do Pop(p, e) end; { SvuotaPila } procedure EsploraPalude (palude : TipoPalude; var trovato : boolean; var cammino : TipoCammino); { Cerca un cammino che porti dalla prima fino all'ultima colonna della palude. } var ri : integer; p : TipoPila; col : TipoColonna; procedure CercaCammino (riga: TipoRiga); { Cerca un cammino a partire dalla prima posizione della riga della palude usando una pila. Se il cammino viene trovato viene memorizzato nella pila stessa. } var pos : TipoPosizione; { variabili esterne utilizzate palude : TipoPalude; trovato : boolean; cammino : TipoCammino; } begin { CercaCammino } pos.riga := riga; pos.colonna := 1; Push(p, pos); { metto nella pila la prima posizione della riga } while (not trovato) and (not TestPilaVuota(p)) do { fino a quando non ho trovato un cammino e ho ancora alternative continuo } begin Pop(p, pos); { estraggo la prossima posizione da visitare } if palude[pos.riga,pos.colonna] = 1 then { se e` di terra } begin cammino[pos.colonna] := pos.riga; { la memorizzo nel cammino } if pos.colonna = C then { se sono arrivato alla fine della palude } begin trovato := TRUE; { forzo la terminazione del ciclo ... } SvuotaPila(p) { e svuoto la pila che non serve piu` } end else { altrimenti } begin { metto nella pila le posizioni ... } pos.colonna := pos.colonna + 1; riga := pos.riga; if riga > 1 then begin pos.riga := riga - 1; Push(p, pos) { sulla riga precedente, ... } end; pos.riga := riga; Push(p, pos); { sulla stessa riga e ... } if riga < R then begin pos.riga := riga + 1; Push(p, pos) { sulla riga successiva } end end end end end; { CercaCammino } begin { EsploraPalude } trovato := FALSE; InitPila(p); { prova a passare per gli elementi della prima colonna, fino a quando non e` stato trovato un cammino } ri := 1; while (not trovato) and (ri <= R) do begin CercaCammino(ri); ri := ri + 1 end; end; { EsploraPalude } procedure StampaCammino (pal: TipoPalude; cammino: TipoCammino); { Stampa su video una palude evidenziando un cammino attraverso asterischi. } var riga : TipoRiga; colonna : TipoColonna; begin writeln('Cammino che attraversa la palude:'); for riga := 1 to R do begin for colonna := 1 to C do begin write(pal[riga,colonna]); { stampa l'elemento della matrice } if riga = cammino[colonna] then { se il punto fa parte del cammino } write('*') { stampa '*' } else { altrimenti } write(' ') { stampa uno spazio } end; writeln end end; { StampaCammino } procedure LeggiPalude (var pal: TipoPalude); { Legge da un file di testo una matrice di 0 e 1 che rappresenta una palude. } var nome_file : string; { nome del file dal quale leggere la matrice } file_matrice : text; { nome del file logico } riga : TipoRiga; { usati come indici dei cicli } colonna : TipoColonna; begin { LeggiPalude } writeln('Nome del file contenente la rappresentazione della palude ?'); readln(nome_file); assign(file_matrice, nome_file); reset(file_matrice); for riga := 1 to R do for colonna := 1 to C do read(file_matrice, pal[riga,colonna]); close(file_matrice) end; { LeggiPalude } procedure StampaPalude (pal: TipoPalude); { Stampa su video una matrice di 0 e 1 che rappresenta una palude. } var riga : TipoRiga; colonna : TipoColonna; begin { StampaPalude } for riga := 1 to R do begin for colonna := 1 to C do write(pal[riga,colonna],' '); writeln end end; { StampaPalude } { variabili utilizzate nel corpo del programma principale } var pal : TipoPalude; { matrice che rappresenta la palude } camm : TipoCammino; { cammino trovato nella palude } trov : boolean; { indica se e` stato trovato un cammino } begin { AttraversaPalude } LeggiPalude(pal); { lettura della matrice da file } writeln('Palude:'); writeln; StampaPalude(pal); { stampa di verifica della matrice } EsploraPalude(pal, trov, camm); { ricerca del cammino } if trov then StampaCammino(pal, camm) else writeln('Non ci sono cammini che attraversano la palude') end. { AttraversaPalude }