{ File: palude4.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 che simula la pila dei record di attivazione
  in una implementazione ricorsiva.
}

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 }

  MaxPila = C;

type
  TipoRiga      = 1..R;
  TipoColonna   = 1..C;
  TipoPalude    = array [TipoRiga, TipoColonna] of 0..1;
  TipoCammino   = array [TipoColonna] of TipoRiga;

  TipoElemPila  = TipoRiga;   { gli elementi della pila sono indici di riga }

{$I PILESEQ.PAS} { Inclusione delle procedure e funzioni per la gestione di pile }


  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
      colonna   : TipoColonna;
      riga_prec : TipoRiga;
      backtrack : boolean;
  { variabili esterne utilizzate
      palude    : TipoPalude;
      trovato   : boolean; }

    begin { CercaCammino }
      Push(p, riga);
      colonna := 1;

      while (not trovato) and (not TestPilaVuota(p)) do
                                   { fino a quando non ho trovato un cammino
                                     e ho ancora alternative continuo }
      begin
        TopPila(p, riga);          { vedo su che riga sono }
        if palude[riga,colonna] = 1 then  { se sono su una posizione di terra }
          if colonna = C then      { se sono arrivato alla fine della palude }
            trovato := TRUE        { ... forzo la terminazione del ciclo }
          else                     { non sono arrivato alla fine della palude }
          begin                    { ... e provo ad andare avanti }
            colonna := colonna + 1;
            if riga > 1 then
              Push(p, riga-1)      { ... sulla riga precedente }
            else
              Push(p, riga)        { ... o sulla stessa riga }
          end
        else                       { se sono su una posizione di mare }
        begin                      { ... devo fare backtrack }
          backtrack := TRUE;
          repeat
            Pop(p, riga);          { ... ritratto l'ultima scelta fatta }
            if (colonna = 1) then      { se ero sulla prima colonna }
              backtrack := FALSE       { ... smetto }
            else                       { altrimenti }
            begin
              TopPila(p, riga_prec);
              if (riga < riga_prec + 1) and (riga < R) then
                                       { ... se ho alternative }
              begin
                Push(p, riga + 1);         { ... provo la prossima }
                backtrack := FALSE         {     e smetto di fare backtrack }
              end
              else                         { altrimenti }
                colonna := colonna - 1     { ... devo tornare indietro }
            end
          until not backtrack
        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;

    if trovato then             { la pila contiene il cammino (al contrario) }
      for col := C downto 1 do  { svuoto la pila e memorizzo il cammino }
        Pop(p, cammino[col])
  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 }