{ 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 }