{ File: labirint.pas }

program ProgrammaLabirinto;

{ Inclusione delle definizioni di labirinto }

{$I LABIRDEF.PAS}

var
  riga, i    : IndiceRiga;
  colonna, j : IndiceColonna;
  filedat    : text;
  labirint   : Labirinto;


  procedure VisitaLabirinto (lab: Labirinto; r: IndiceRiga; c: IndiceColonna);
  { Visita il labirinto a partire dal punto di entrata r,c.
    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 l) e
    assegna il parametro Trovato di VisitaLabirinto opportunamente.
   
    Per memorizzare il cammino di attraversamento non possiamo che far uso di
    un vettore. Lo chiamiamo "cammino" e lo dimensioniamo in modo che possa
    contenere qualunque cammino possibile: il cammino piu` lungo per uscire da
    un labirinto avente solo i muri perimetrali - con 1 entrata e una uscita -
    e niente all'interno, e' nm-2m-2n+6. }

    const
      NCAMM = n * m - 2 * m - 2 * n + 6;
    type
      TNcamm = 1..NCAMM;

    var
      k1, k2          : integer;
      marcheLabirinto : array [IndiceRiga, IndiceColonna] of boolean;
      trovato         : boolean;
      cammino         : array [TNcamm] of record
                                            coordi : IndiceRiga;
                                            coordj : IndiceColonna;
                                          end;
  
    { variabile di tipo molto "ad hoc" per contenere il cammino ciascun
      elemento rappresenta un punto del cammino percorso. Il cammino termina
      con successo quando contiene un punto di passaggio con coordi=N o 1
      oppure coordj=M o 1. Gli elementi successivi del cammino verranno
      ignorati da una eventuale stampa. }

    procedure RicercaCammino (i: IndiceRiga; j: IndiceColonna;
                              var trovato: boolean; ultimocamm: TNcamm);

    { usa le variabili non locali:
      - lab (parametro di VisitaLabirinto)
      - trovato (var locale di VisitaLabirinto)
      - marchelabirinto (")
      - cammino         (")
      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 }
           cammino[ultimocamm].coordi := i;
           cammino[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 sarˆ un punto esistente e di passaggio e non
             ancora visitato, andra` aggiunto nel cammino nella posizione
             successiva.
                
             Immaginiamo non sia ammesso muoversi in diagonale (chiamate
             poste in commento).
                
             Notare che modificando l'ordine delle chiamate si possono
             organizzare delle vere e proprie strategie di ricerca del percorso
             (prima a destra poi in alto oppure prima in alto e poi a destra
             ... etc...). }

           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;

    { attraversamento ancora non trovato }
    trovato := FALSE;


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

    if trovato then
    begin
      writeln('cammino trovato ...');
      write('(', cammino[1].coordi, ',', cammino[1].coordj, ') ');
      k1 := 1;
      repeat
        k1 := k1 + 1;
        write('(', cammino[k1].coordi, ',', cammino[k1].coordj, ') ');
      until (cammino[k1].coordi = 1) or (cammino[k1].coordj = 1)
      or (cammino[k1].coordi = N) or (cammino[k1].coordj = M);
      writeln;
    end
    else writeln('nessun cammino trovato');
  end; { VisitaLabirinto }


begin { ProgrammaLabirinto }
  assign(filedat, 'a:labirint.dat');
  Leggilabirinto(filedat, labirint);
  stampalabirinto(labirint);
  writeln;
  writeln('punto di entrata ?');
  readln(riga, colonna);
  writeln;
  VisitaLabirinto(labirint, riga, colonna);
  writeln('fine');
  readln
end. { ProgrammaLabirinto }