{ File: palude2.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 nella quale sono possibili movimenti in tutte le direzioni
  (senza superare i confini della palude).
}

const
  R = 5;                    { numero di righe, cioe` larghezza della palude   }
  C = 7;                    { numero di colonne, cioe` lunghezza della palude }
  MaxLunghezzaCammino = 35; { 5*7 }           { questo e` un limite superiore }

type
  TipoRiga          = 1..R;
  TipoColonna       = 1..C;
  TipoIndiceCammino = 1..MaxLunghezzaCammino;
  TipoPosizione     = record
                        riga    : TipoRiga;
                        colonna : TipoColonna
                      end;      
  TipoPalude        = array [TipoRiga, TipoColonna] of 0..1;
  TipoCammino       = record
                        lunghezza : 0..MaxLunghezzaCammino;
                        posizioni : array [TipoIndiceCammino] of TipoPosizione
                      end;


  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 (i: TipoRiga; j: TipoColonna);
    { Cerca un cammino a partire dalla posizione <i,j> della palude. }

    { variabili esterne utilizzate
        palude  : TipoPalude;
        trovato : boolean;
        cammino : TipoCammino;
    }
    begin
      if palude[i,j] = 1 then
      begin
        cammino.lunghezza := cammino.lunghezza + 1;
        with cammino.posizioni[cammino.lunghezza] do
        begin
          riga := i;
          colonna := j
        end;

        palude[i,j] := 0;      { marca la posizione come visitata in modo da
                                 non considerarla per passaggi successivi }
        if j >= C then         { sono arrivato dall'altra parte della palude }
          trovato := TRUE
        else                   { cerco un passaggio nella posizioni adiacenti }
        begin
          if i > 1 then                     { se non sono sulla prima riga    }
            CercaCammino(i-1, j+1);         {   provo con <i-1,j+1>           }
          if (not trovato) then
            CercaCammino(i, j+1);           {   provo con <i,j+1>             }
          if (not trovato) and (i < R) then { se non sono sull'ultima riga    }
            CercaCammino(i+1, j+1);         {   provo con <i+1,j+1>           }
          if j > 2 then                     { se non sono sulla seconda colonna }
          begin
            if (not trovato) and (i > 1) then { se non sono sulla prima riga  }
              CercaCammino(i-1, j);           {   provo con <i-1,j>           }
            if (not trovato) and (i < R) then { se non sono sull'ultima riga  }
              CercaCammino(i+1, j);           {   provo con <i+1,j>           }
            if (not trovato) and (i > 1) then { se non sono sulla prima riga  }
              CercaCammino(i-1, j-1);         {   provo con <i-1,j-1>         }
            if (not trovato) then
              CercaCammino(i, j-1);           {   provo con <i,j-1>           }
            if (not trovato) and (i < R) then { se non sono sull'ultima riga  }
              CercaCammino(i+1, j-1);         {   provo con <i+1,j-1>         }
          end;
          if not trovato then
            cammino.lunghezza := cammino.lunghezza - 1
        end
      end
    end; { CercaCammino }

  begin { EsploraPalude }
    trovato := FALSE;
    cammino.lunghezza := 0;    { inizialmente il cammino ha lunghezza nulla }

    { 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 (cammino: TipoCammino);
  { Stampa su video la sequenza delle posizioni di un cammino. }
  var
    posizione : 0..MaxLunghezzaCammino;

  begin
    writeln('Cammino che attraversa la palude:');
    for posizione := 1 to cammino.lunghezza do
      with cammino.posizioni[posizione] do
        writeln('<', riga, ',', colonna, '>')
  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(camm)
  else
    writeln('Non ci sono cammini che attraversano la palude')
end. { AttraversaPalude }