{ File: palude.pas } { Scopo: esercizio significativo sulla ricorsione } 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) } 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; 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; procedure CercaCammino (riga: TipoRiga; colonna: TipoColonna); { Cerca un cammino a partire dalla posizione <riga,colonna> della palude. } { variabili esterne utilizzate palude : TipoPalude; trovato : boolean; cammino : TipoCammino; } begin if palude[riga,colonna] = 1 then begin cammino[colonna] := riga; if colonna >= C then { sono arrivato dall'altra parte della palude } trovato := TRUE else { cerco un passaggio nella colonna+1 } begin if riga > 1 then { non sono sulla prima riga } CercaCammino(riga-1, colonna+1); { provo la posizione <riga-1,colonna+1> } if (not trovato) then CercaCammino(riga, colonna+1); { provo la posizione <riga,colonna+1> } if (not trovato) and (riga < R) then { non sono sull'ultima riga } CercaCammino(riga+1, colonna+1); { provo la posizione <riga+1,colonn+1> } end end end; { CercaCammino } begin { EsploraPalude } trovato := FALSE; { 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, 1); 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 }