# Informatica 2 Liceo Scientifico Scienze Applicate/MappaAntica

Informatica 2 Liceo Scientifico Scienze Applicate
Copertina Tutti i moduli · Sviluppo
* Linguaggi di programmazioneInformatica 2 Liceo Scientifico Scienze Applicate/Linguaggi di programmazione
* Compilare un programmaInformatica 2 Liceo Scientifico Scienze Applicate/Compilare un programma
* CiaoMondoInformatica 2 Liceo Scientifico Scienze Applicate/CiaoMondo
* AreaRettangoloInformatica 2 Liceo Scientifico Scienze Applicate/AreaRettangolo
* AreaTrapezioInformatica 2 Liceo Scientifico Scienze Applicate/AreaTrapezio
** Compito1Informatica 2 Liceo Scientifico Scienze Applicate/Compito1
* Programmazione ImperativaInformatica 2 Liceo Scientifico Scienze Applicate/Programmazione Imperativa
* Diagrammi di FlussoInformatica 2 Liceo Scientifico Scienze Applicate/Diagrammi di Flusso
* Operatori AritmeticiInformatica 2 Liceo Scientifico Scienze Applicate/Operatori Aritmetici
* Istruzione ifInformatica 2 Liceo Scientifico Scienze Applicate/Istruzione if
** Esercizio Equazione 2^ gradoInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio Equazione 2^ grado
** Esercizio Calcola lo ScontoInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio Calcola lo Sconto
** Esercizio Calcola lo Sconto2Informatica 2 Liceo Scientifico Scienze Applicate/Esercizio Calcola lo Sconto2
* Operatori LogiciInformatica 2 Liceo Scientifico Scienze Applicate/Operatori Logici
** Esercizio x interno all'intervalloInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio x interno all'intervallo
** Esercizio x esterno all'intervalloInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio x esterno all'intervallo
* Istruzione switchInformatica 2 Liceo Scientifico Scienze Applicate/Istruzione switch
** Esercizio Scelta EquazioneInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio Scelta Equazione
* Altre Istruzioni di Scelta o DiramazioneInformatica 2 Liceo Scientifico Scienze Applicate/Altre Istruzioni di Scelta o Diramazione
* Istruzioni di RipetizioneInformatica 2 Liceo Scientifico Scienze Applicate/Istruzioni di Ripetizione
** Es (do-while) Indovina il numeroInformatica 2 Liceo Scientifico Scienze Applicate/Es (do-while) Indovina il numero
** Es (while) La nonna è stancaInformatica 2 Liceo Scientifico Scienze Applicate/Es (while) La nonna è stanca
** Es (for) Somma di 5 numeriInformatica 2 Liceo Scientifico Scienze Applicate/Es (for) Somma di 5 numeri
** Es (for) Analisi sequenza datiInformatica 2 Liceo Scientifico Scienze Applicate/Es (for) Analisi sequenza dati
** Es (for) Sequenze NumericheInformatica 2 Liceo Scientifico Scienze Applicate/Es (for) Sequenze Numeriche
** Es (for) SupermarketInformatica 2 Liceo Scientifico Scienze Applicate/Es (for) Supermarket
** Es (while) Bisca ClandestinaInformatica 2 Liceo Scientifico Scienze Applicate/Es (while) Bisca Clandestina
* Compito2Informatica 2 Liceo Scientifico Scienze Applicate/Compito2
* I vettoriInformatica 2 Liceo Scientifico Scienze Applicate/I vettori
** Es Usiamo i vettoriInformatica 2 Liceo Scientifico Scienze Applicate/Es Usiamo i vettori
** Es2 Usiamo i vettoriInformatica 2 Liceo Scientifico Scienze Applicate/Es2 Usiamo i vettori
** Es3 Supermarket con vettoriInformatica 2 Liceo Scientifico Scienze Applicate/Es3 Supermarket con vettori
** Compito dic 2019Informatica 2 Liceo Scientifico Scienze Applicate/Compito dic 2019
** BubbleSortInformatica 2 Liceo Scientifico Scienze Applicate/BubbleSort
** Ricerca DicotomicaInformatica 2 Liceo Scientifico Scienze Applicate/Ricerca Dicotomica
* Matrici e ArrayInformatica 2 Liceo Scientifico Scienze Applicate/Matrici e Array
** Es matrici battaglia navaleInformatica 2 Liceo Scientifico Scienze Applicate/Es matrici battaglia navale
** Es matrici 1Informatica 2 Liceo Scientifico Scienze Applicate/Es matrici 1
** Es matrici 2Informatica 2 Liceo Scientifico Scienze Applicate/Es matrici 2
* PuntatoriInformatica 2 Liceo Scientifico Scienze Applicate/Puntatori
* StructInformatica 2 Liceo Scientifico Scienze Applicate/Struct
** Es Bubble Sort con StructInformatica 2 Liceo Scientifico Scienze Applicate/Es Bubble Sort con Struct
* FunzioniInformatica 2 Liceo Scientifico Scienze Applicate/Funzioni
* Funzioni Void e non VoidInformatica 2 Liceo Scientifico Scienze Applicate/Funzioni Void e non Void
** esercizi1 funzioniInformatica 2 Liceo Scientifico Scienze Applicate/esercizi1 funzioni
** esercizi2 funzioniInformatica 2 Liceo Scientifico Scienze Applicate/esercizi2 funzioni
** esercizi3 funzioniInformatica 2 Liceo Scientifico Scienze Applicate/esercizi3 funzioni
* BacktrackingInformatica 2 Liceo Scientifico Scienze Applicate/Backtracking
* TemplateInformatica 2 Liceo Scientifico Scienze Applicate/Template
* FileInformatica 2 Liceo Scientifico Scienze Applicate/File
** File di TestoInformatica 2 Liceo Scientifico Scienze Applicate/File di Testo
** File BinariInformatica 2 Liceo Scientifico Scienze Applicate/File Binari
** File RecordsInformatica 2 Liceo Scientifico Scienze Applicate/File Records
** Es FilesInformatica 2 Liceo Scientifico Scienze Applicate/Es Files
* Esercizi VacanzeInformatica 2 Liceo Scientifico Scienze Applicate/Esercizi Vacanze
** Esercizi1Informatica 2 Liceo Scientifico Scienze Applicate/Esercizi1
** Esercizi2Informatica 2 Liceo Scientifico Scienze Applicate/Esercizi2
** Esercizi3Informatica 2 Liceo Scientifico Scienze Applicate/Esercizi3
* Olimpiadi Informatica
** NobileChimicoInformatica 2 Liceo Scientifico Scienze Applicate/NobileChimico
** Sunnydale
** MappaAnticaInformatica 2 Liceo Scientifico Scienze Applicate/MappaAntica
Modifica il sommario

### 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 |
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.
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:
gli spiazzamenti (traslazioni ,offset) rispetto a (i,j) sono:
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:
* 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