Informatica 2 Liceo Scientifico Scienze Applicate/MappaAntica

Mappa Antica

Descrizione del problema:
Topolino è in missione per accompagnare una spedizione archeologica che segue un'antica mappa acquisita di recente dal museo di Topolinia. Raggiunta la località dove dovrebbe trovarsi un prezioso e raro reperto archeologico, Topolino si imbatte in un labirinto che ha la forma di una gigantesca scacchiera quadrata di NxN lastroni di marmo.
Nella mappa, sia le righe che le colonne del labirinto sono numerate da 1 a N. Il lastrone che si trova nella posizione corrispondente alla riga r e alla colonna c viene identificato mediante la coppia di interi (r, c). I lastroni segnalati da una crocetta '+' sulla mappa contengono un trabocchetto mortale e sono quindi da evitare, mentre i rimanenti sono innocui e segnalati da un asterisco '*'.
Topolino deve partire dal lastrone in posizione (1, 1) e raggiungere il lastrone in posizione (N, N), entrambi innocui. Può passare da un lastrone a un altro soltanto se questi condividono un lato o uno spigolo (quindi può procedere in direzione orizzontale, verticale o diagonale ma non saltare) e, ovviamente, questi lastroni devono essere innocui.
Tuttavia, le insidie non sono finite qui: per poter attraversare incolume il labirinto, Topolino deve calpestare il minor numero possibile di lastroni innocui (e ovviamente nessun lastrone con trabocchetto). Aiutate Topolino a calcolare tale numero minimo..

Dati di input

Il file input.txt è composto da N+1 righe.
La prima riga contiene un intero positivo che rappresenta la dimensione N di un lato del labirinto a scacchiera.
Le successive N righe rappresentano il labirinto a scacchiera: la r-esima di tali righe contiene una sequenza di N caratteri '+' oppure '*', dove '+' indica un lastrone con trabocchetto mentre '*' indica un lastrone sicuro. Tale riga rappresenta quindi i lastroni che si trovano sulla r-esima riga della schacchiera: di conseguenza, il c-esimo carattere corrisponde al lastrone in posizione (r, c).

Dati di output

Il file output.txt è composto da una sola riga contenente un intero che rappresenta il minimo numero di lastroni innocui (ossia indicati con '*') che Topolino deve attraversare a partire dal lastrone in posizione (1, 1) per arrivare incolume al lastrone in posizione (N, N). Notare che i lastroni (1, 1) e (N, N) vanno inclusi nel conteggio dei lastroni attraversati.

Assunzioni

• • 1 ≤N≤ 100
• • 1 ≤r, c≤N
• • E' sempre possibile attraversare il labirinto dal lastrone in posizione (1, 1) al lastrone in posizione (N, N); inoltre tali due lastroni sono innocui.
  

Esempi di input/output

File input.txt	File output.txt
4	5
*+++
+**+
+*+*
+****

#include <iostream>
#include <fstream>
using namespace std;
int m[100][100];
int n;
int delta[8][2]={ -1,-1,
                  -1, 0,
                  -1,+1,
                   0,-1,
                   0,+1,
                  +1,-1,
                  +1, 0,
                  +1,+1
               };

void sposta( int x, int y)
{ int i,xn,yn;
  for(i=0;i<8;i++)
    { xn=x+delta[i][0];
      yn=y+delta[ij[1];
      /* xn e yn sono le coordinate della cella in cui voglio spostarmi
      xn>0 && xn<=n && yn>0 && yn<=n  servono per verificare che le coordinate
      xn e yn siano comprese fra 1 e n (che rappresentano il labirinto)
      m[xn][yn]!='-1'   non posso andare sulle celle della morte
      m[xn][yn]>m[x][y]+1    significa che il percorso dalla cella x y a cui aggiungo
      un passo è minore del percorso  che avevo registrato precedentemente per arrivare nella cella xn yn
      quindi se trovo un percorso più breve aggiorno il valore della cella xn yn e 
      rianalizzo la situazione partendo da xn yn, per vedere se il percorso
      più breve appena trovato permette di migliora a sua volta i percorsi attorno a xn yn
      (per fare questo uso la ricorsione)
	  */
      if(xn>0 && xn<=n && yn>0 && yn<=n && m[xn][yn]!='-1' && m[xn][yn]>m[x][y]+1)
       { m[xn][yn]=m[x][y]+1;
         sposta(xn,yn);
	   }
	}
}


int main(int argc, char** argv) 
{ int i,j;
  char c;
  ifstream fi;
  fi.open("input.txt");
  fi>>n;
  for(i=1;i<=n;i++) // l'esercizio parla di cella 1,1
                    // se pongo i=0 bisogna riscalare 
                    // griglia del labirinto e condizioni su di essa
                    
   for(j=1;j<=n;j++)
    {fi>>c;
       if(c=='+')
         m[i][j]= -1;  // -1 uguale a morte
       else
	     m[i][j]= 999; // 999 significa cella visitabile
		               // attualmente con un numero di passi
					   // grandissimo (teoricamente infinito)
	}
  fi.close();  
  m[1][1]=1; // si conta la cella di partenza come primo passo
  sposta(1,1);// parto dalla cella 1,1
  

  ofstream fo;
  fo.open("output.txt");
  fo<<m[n][n];
  fo.close();
	
	return 0;
}

Descrizione della soluzione :

La soluzione proposta è una soluzione ricorsiva, non la più veloce ma è interessante per verificare la comprensione della tecnica del backtracking visto con il problema delle 8 regine. Per rappresentare il problema si usa una matrice N*N (nel codice si usa una matrice globale 100*100 di cui si usano le celle da (1,1) a (N,N) la matrice è globale e sovradimensionata per evitare di passarla alla funzione ricorsiva come parametro, come pure è globale il parametro N ), nella matrice uso il valore -1 per indicare che la cella non è accessibile ( trabocchetto +), in quelle accessibili inserisco un numero che rappresenta il percorso minimo per arrivare in quella cella, inizialmente la cella di partenza (1,1) viene messa a 1 perché il conteggio tiene conto anche della cella di partenza, inizialmente nelle altre celle accessibili viene messo il numero 999 (nella realtà dovrei mettere infinito o se volete INT_MAX) che indica che non sono riuscito ancora a spostarmi in quella.

Modello della mappa

Durante l'esecuzione del programma la funzione ricorsiva sposta(x,y) riceve una cella da analizzare, pensiamo sia la cella (x,y) nella quale m(x,y) rappresenta il numero di passi per arrivarci, la funzione ricorsiva analizza le celle adiacenti (una alla volta) e se con un ulteriore passo rispetto a m(x,y) posso accorciare il percorso m(nx,ny) per arrivare nella cella adiacente (nx,ny) aggiorno il valore di m(nx,ny) con il valore m(x,y)+1 ogni cella (nx,ny) aggiornata viene quindi rianalizzata da un'altra funzione ricorsiva sposta(nx,ny) per vedere se a sua volta permette di accorciare le distanze per raggiungere una cella adiacente a (nx,ny). La funzione ricorsiva termina una volta analizzate tutte le sue celle adiacenti.

Per trovare le celle adiacenti a (i,j) basta vedere questa relazione:

coordinate relative delle celle adiacenti a quella (i,j)

gli spiazzamenti (traslazioni ,offset) rispetto a (i,j) sono:

Offset da (i,j)

I valori degli offset (traslazione/spiazzamenti) sono stati inseriti nella matrice 8*2 dove 8 sono le possibili celle adiacenti e le due colonne rappresentano il Δi e il Δj

La ricorsione funziona in questo modo:

aggiornamento ricorsivo

• nella prima immagine in giallo la cella (x,y) che la funzione ricorsiva sposta(x,y) vuole gestire e in arancione le 8 celle adiacenti
• nella seconda immagine, delle 8 celle adiacenti solo 4 sono migliorabili (escludo quelle con celle non accessibili, quelle fuori dalla mappa e quelle con m[xn][yn]<= m[x][y]+1)
• nella terza immagine pensiamo di aggiornare una delle 4 celle ad esempio la cella che ora assume il valore 5 (in giallo), aggiornato il valore m[xn][yn] viene lanciata una nuova funzione ricorsiva tramite la chiamata sposta(xn,yn) che analizzerà la situazione attorno a xn,yn (celle in arancione) modificando ad esempio il valore da 20 a 6 e anche quella da 56 a 6 (il disegno non lo riporta)
• una volta che questa termina il controllo ritorna alla funzione ricorsiva sposta(x,y) che deve completare l'analizzarei delle celle adiacenti

nell'ultimo disegno la situazione finale