{ File: lab2.pas }

program ProgrammaLabirinto2;

{ Questa volta le costanti significative del programma sono poste
  in questo file, in modo da renderle piu' facilmente modificabili. }

const
  N              = 10;
  M              = 15;
  PASSAGGIO      = '-';	{ carattere che indica un punto di passaggio nel
                          labirinto }
  EVIDENTE = ' ';	{ carattere che evidenzia un punto di passaggio
                          nel percorso attraverso il labirinto }

{ Ora includiamo il file con le definizioni. Si tratta di un file piu'
  esteso di LABIRINT.DEF, con definizioni anche per il tipo ATTRAVERSAMENTO
  e di due procedure per la stampa di una variabile di tipo ATTRAVERSAMENTO
  e per il riversamento in una matrice LABIRINTO di un attraversamento. }

{$I LABDEF2.PAS}

var
  riga, i    : INDICERIGA;       { per scandire le righe del labirinto }
  colonna, j : INDICECOLONNA;    { per scandire le colonne del labirinto }
  filedat    : text;             { filedati per il labirinto }
  labirint   : LABIRINTO;        { matrice labirinto }
  percorso   : ATTRAVERSAMENTO;  { vettore per il percorso }
  trovato    : boolean;          { =TRUE se si e' trovato un percorso }


  procedure VisitaLabirinto (lab: labirinto; r: INDICERIGA; c: INDICECOLONNA;
                             var trovato: boolean; var att: ATTRAVERSAMENTO);

  { Visita il labirinto lab a partire dal punto di entrata (r,c) e memorizza
    il percorso trovato (se trovato) nell'array att.
    Il parametro "trovato" viene assegnato a TRUE/FALSE se e' stato
    trovato/non-trovato un percorso effettivo.

    Una uscita e' un punto di passaggio con coordinata i=1 o i=n
    o j=1 o j=m, che sia diverso da (r,c).
     
    La procedura controlla se il punto di entrata e' effettivamente di
    passaggio e poi procede lanciando la RicercaCammino su ogni punto
    adiacente che sia di passaggio.
    RicercaCammino marca il punto da cui sta partendo nella matrice
    marchelabirinto (per evitare di far ripartire ricerche da li') e
    assegna il parametro Trovato di VisitaLabirinto opportunamente
    }

  var
    k1, k2          : integer;
    marcheLabirinto : array [INDICERIGA, INDICECOLONNA] of boolean;


    procedure RicercaCammino (i: indiceriga;
                              j: indicecolonna;
                              var trovato: boolean;
                              ultimocamm: TNcamm);
    { Usa le variabili non locali:
         - lab             (parametro di VisitaLabirinto)
         - trovato         (parametro di VisitaLabirinto)
         - marchelabirinto (variabile locale di VisitaLabirinto)
         - att             (parametro di VisitaLabirinto)
        
      Il parametro ultimocamm dice in quale componente di cammino va
      memorizzato il nuovo elemento i,j; le prossime aggiunte
      lungo il cammino andranno fatte da ultimocamm+1 in poi. }

    begin  { RicercaCammino }
      {writeln('   ricerca ', i : 2, j : 2);}
      if (i >= 1) and (i <= N) and (j > 0) and (j <= M) then
        { Il punto esiste.
          Se e' gia' stato visitato o non e' di passaggio,
            non bisogna fare nulla.
 	  Se e' un punto di passaggio non ancora visitato,
 	    allora bisogna inserirlo nel cammino e attivare la ricerca sui
            punti adiacenti. }

        if (not marchelabirinto[i, j]) and (lab[i,j] = PASSAGGIO) then
        begin  { *** }
          { inserisce il punto nel cammino }
          att[ultimocamm].coordi := i;
          att[ultimocamm].coordj := j;

          { marca questo punto del labirinto }
          marchelabirinto[i, j] := TRUE;

          { determina se il punto e` conclusivo }
          if (i = 1) or (i = N) or (j = 1) or (j = M) then
            if not ((i = r) and (j = c)) then
              { non e' il punto di entrata: va bene }
              trovato := TRUE;

          { Se non e' trovato=TRUE bisogna cercare il cammino a partire da uno
            dei punti intorno a quello attuale.
            Il nuovo punto del cammino - se sara` un punto esistente e di
            passaggio e non ancora visitato, andra` aggiunto nel cammino nella
            posizione successiva.
                 
            Immaginiamo non sia ammesso muoversi in diagonale (per permetterlo
            basta de-commentare le chiamate poste in commento).
                 
            Notare che modificando l'ordine delle chiamate si possono
            organizzare delle vere e proprie strategie di ricerca
            (ad esempio, usando la matrice labirint.dat, la procedura
            attuale trova un percorso uscente a destra del labirinto.
            Questo perche` nelle chiamate di RicercaCammino si da` la
            precedenza agli spostamenti verso destra e poi agli altri;
            invertendo l'ordine delle prime due chiamate qui sotto, la
            procedura trova un percorso diverso). }

          if not trovato then
            RicercaCammino(i, j + 1, trovato, ultimocamm + 1);

        { if not trovato then
            RicercaCammino(i - 1, j + 1, trovato, ultimocamm + 1); }

        { if not trovato then
            RicercaCammino ( i + 1 , j + 1 , trovato , ultimocamm + 1 ); }

          if not trovato then
            RicercaCammino(i + 1, j, trovato, ultimocamm + 1);

          if not trovato then
            RicercaCammino(i - 1, j, trovato, ultimocamm + 1);

          if not trovato then
            RicercaCammino(i, j - 1, trovato, ultimocamm + 1);

        { if not trovato then
            RicercaCammino ( i - 1 , j - 1 , trovato , ultimocamm + 1 ); }

        { if not trovato then
            RicercaCammino(i + 1, j - 1, trovato, ultimocamm + 1); }

        end; { *** }
    end; { RicercaCammino }


  begin  { VisitaLabirinto }

    { Init marchelabirinto: FALSE = "il punto non e`
      stato visitato"; i punti visitati verranno marcati con TRUE da
      RicercaCammino }
    for k1 := 1 to N do
      for k2 := 1 to M do
        marcheLabirinto[k1, k2] := FALSE;

    { Inizio ricerca cammino dal punto di entrata
      inserire in cammino[1] il nuovo elemento del cammino }
    RicercaCammino(r, c, trovato, 1);
  end; { VisitaLabirinto }


begin { ProgrammaLabirinto2 }
  assign(filedat, 'a:labirint.dat');
  Leggilabirinto(filedat, labirint);
  stampalabirinto(labirint);
  writeln;
  writeln('punto di entrata ?');
  readln(riga, colonna);
  writeln;
  { attraversamento ancora non trovato }
  trovato := FALSE;
  VisitaLabirinto(labirint, riga, colonna, trovato, percorso);
  if trovato then
  begin
    StampaAttraversamento(percorso, 4);
    StampaPercorsoSuLabirinto(labirint, percorso)
  end
  else
    writeln('nessun cammino trovato')
end. { ProgrammaLabirinto2 }