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