Il Linguaggio C++.

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 ad 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 scacchiera: 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.
• È sempre possibile attraversare il labirinto dal lastrone in posizione (1, 1) al lastrone in posizione (N, N); inoltre tali due lastroni sono innocui.

Esempio di input/output

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

---

Dati di Input

In questa sezione si illustra il procedimento per fornire i dati di input al programma.

Si prepari, usando Blocco Note, un file denominato input.txt contenente le stesse righe usate nell'esempio.

Aprire un nuovo progetto, denominarlo Mappe.
Nella funzione main scrivere le seguenti dichiarazioni:

una variabile intera N, un array di (massimo) 100x100 caratteri, un puntatore pf al file.

Leggere i dati dal file:

La prima riga del file contiene un numero intero da trasferire nella variabile N.

Le N righe successive contengono stringhe di caratteri + e *, che si possono leggere utilizzando la funzione fscanf:

si deve notare che, quando si legge da file, la funzione fscanf richiede che venga specificato l'indirizzo della variabile in cui memorizzare il valore letto. Poichè M è una matrice bidimensionale, nel linguaggio C esiste la regola che se non si specifica una coordinata, il compilatore usa l'indirizzo della matrice, a iniziare dalla coordinata specificata.

Quindi M[r] si riferisce all'indirizzo della riga r.

Ogni riga (un record) letta dal file viene scritta in una riga della matrice, non è necessario leggere carattere per carattere.

---

Esempio

Partendo dalla casella 0, 0 si può proseguire nella casella 1, 1. Siccome la casella (0, 0) ha un solo successore, si fa un passo sulla casella (1, 1).

	0	1	2	3
0	*	+	+	+
1	+	*	*	+
2	+	*	+	*
3	+	*	*	*

dalla casella di coordinate 1, 1 ci si può spostare sia nella casella in coordinate 1, 2 che nella casella in coordinate 2, 1.

dalla casella di coordinate 1, 1 non si deve considerare la casella in coordinate 0, 0 perchè è quella di provenienza.

Mentre si esaminano tutte le caselle che si trovano intorno a quella corrente, ogni volta che si trova una casella contrassegnata da * si memorizzano le sue coordinate sullo stack, purchè non sia stata già attraversata, infatti significherebbe raggiungerla tramite un percorso più lungo.

Quindi, al termine dell'esame di tutte le direzioni si prelevano dallo stack le coordinate di una casella e si ripete l'analisi delle direzioni consentite a partire da questa casella.

Ci si sposti prima sulla casella (1, 2), si vede che si può proseguire nella (2, 3), nella (1, 1) e nella (2, 1).

La casella di coordinate (1, 1) si scarta perchè è quella di provenienza, la casella (2, 1) si scarta perchè è raggiungibile dalla (1, 1) tramite un percorso di lunghezza minore.

Ci si sposti sull'altra casella raggiungibile dalla (1, 1), cioè la (2, 1). Si vede che ci sono quattro possibili direzioni, due delle quali raggiungibili con un percorso più breve, e quindi scartate, le altre due, invece, memorizzate sullo stack, sono le caselle (3, 1) e (3, 2).

A questo punto sullo stack sono presenti i nodi: (2, 3), (3, 1) e (3, 2).

Dalla casella (2, 3) ci si può spostare nella (3, 3) e nella (3, 2) che però si scarta.

Dalla casella (3, 1) ci si può spostare su caselle già raggiunte quindi si scarta.

Dalla casella (3, 2) ci si può spostare nella (3, 3) e nelle caselle: (3, 1), (2, 1) e (2, 3) che però si scartano.

Si è ottenuto un grafo orientato che può essere memorizzato come albero.

Memorizzazione dell'Albero: Ogni nodo dell'albero è un record che deve contenere le informazioni specificate nelle intestazioni di colonna della seguente tabella:

	Coordinate	Numero Casella	Precedente
0	0, 0	0	nessuno
1	1, 1	5	0
2	2, 1	9	1
3	1, 2	6	1
4	3, 1	13	2
5	3, 2	14	2
6	2, 3	11	3
7	3, 3	15	5
8	3, 3	15	6

Un Albero è un insieme di nodi da ognuno dei quali partono archi verso altri nodi, che sono detti successori. Uno dei nodi è detto Radice perchè non è successore di nessun altro nodo. Ognuno dei nodi successori è Radice di un sottoalbero.

Il livello di un nodo è il numero di nodi che lo separano dalla radice dell'albero. La definizione di albero è ricorsiva, cioè definita in termini di se stesso.

Quindi altre variabili da impiegare sono un array, utilizzato come stack, ed un indice, utilizzato come puntatore allo stack.

L'accesso allo stack deve essere effettuato tramite due funzioni: inserisci() e preleva().

---

Analisi del problema

Si suppone che nella variabile N sia stato acquisito il numero di righe da leggere dal file e, quindi, di aver acquisito i dati dal file di input. I caratteri "*" (asterisco) e "+" (più) sono stati trasferiti dal file alla matrice M, dimensionata per contenere 100 righe x 100 colonne, al massimo.

Le coordinate delle caselle della matrice M possono essere associate con una numerazione progressiva che assegna il numero 0 alla casella di coordinate (0, 0), il numero 1 alla casella di coordinate (0, 1) e prosegue numerando tutte le caselle della riga 0. Poi la numerazione continua dal primo elemento della riga successiva.

	0	1	2	3
0	0	1	2	3
1	4	5	6	7
2	8	9	10	11
3	12	13	14	15

La relazione che lega le coordinate di Riga e di Colonna a una tale numerazione è:

dove N è una dimensione della matrice quadrata.

Procedimento risolutivo:

Un primo schema di algoritmo risolutivo potrebbe essere il seguente:

I nodi di uno stesso livello si trovano nell'albero a partire dalla riga il cui valore è specificato nella variabile Pross fino alla riga Pross+Conta, dove la variabile Conta contiene il numero di successori dei nodi di uno stesso livello.

	Riga	Colonna	Successore di
Pross →	0	0	-1

A) Per tutti i nodi di uno stesso livello:

• Leggere le coordinate di riga r e di colonna c della casella,

• Tramite le coordinate di riga e di colonna determinare le coordinate delle caselle adiacenti,

• Se la casella adiacente contiene un * e se non è stata già inserita nell'albero, Inserire sullo stack le coordinate di questa casella e l'indice di riga della tabella Albero in cui è stato memorizzato il nodo padre.

Per verificare se le coordinate di una casella sono già state inserite nell'albero si devono confrontare le coordinate di questa casella con le coordinate memorizzate nella tabella Albero tra la riga 0 e la riga corrente. Se si trova che le coordinate di questa casella sono presenti nell'albero significa che questa casella è stata raggiunta attraverso un percorso più breve, e quindi deve essere scartata.

A questo punto sullo stack sono stati memorizzati tutti i successori di uno stesso nodo.

Prelevare dallo stack le coordinate di una casella e l'indice di riga del Padre:

• Inserire queste informazioni nell'albero,

• contare un successore,

• ripetere dal punto A) fino a quando lo stack diventa vuoto.

Nell'albero sono stati inseriti i nodi e sono stati collegati al Padre.

Prima di determinare i successori di ciascuno di questi nodi si deve calcolare la prossima riga da cui iniziare ad inserire i nodi successori di quelli che si stanno per esaminare.

• Incrementare, di una quantità pari al numero di successori, l'indice di riga dell'albero da cui inizierà la costruzione di un sottoalbero
  Pross → Pross + Numero di successori.

• Se non si è giunti alla casella terminale ripetere dal punto A).

Quando si giunge alla casella terminale si deve risalire l'albero dalle foglie verso la radice e contare il numero di passi.

Ovviamente ci potrebbero essere 1, 2 o 3 direzioni da cui si giunge nella casella terminale. (il caso 0 è escluso)

Quindi nell'albero bisogna cercare solo le foglie che corrispondono alla casella terminale.

sono stati trovati solo i percorsi di lunghezza minima.

---

Lo stack

Lo stack è una struttura dati che in questo esempio viene dichiarata come variabile globale:

La funzione Inserisci riceve i parametri da depositare sullo stack (si dovrebbe verificare se lo stack è pieno) e non restituisce nessun risultato.

La funzione Preleva riceve i riferimenti alle variabili in cui trasferire i valori prelevati dallo stack. Si verifica se lo stack è vuoto e si restituisce vero se l'operazione è riuscita e falso se lo stack è vuoto.

---

il programma principale

Altre variabili globali sono:

Che servono per memorizzare i nodi da collegare ad Albero, e l'indice al nodo dell'albero di cui si devono trovare i successori.

Inoltre serve una funzione che determina se un casella è stata già inserita nell'albero:

La funzione NonCe restituisce vero se la casella non è presente nell'albero e falso se invece è presente.

Le variabili locali alla funzione main sono:

dove:

• Corrente viene usata per memorizzare l'indice del nodo padre.

• la variabile intera NrPassi conta il numero di caselle da attraversare per raggiungere la casella terminale,

• La variabile Conta è il contatore dei successori di un nodo.

Vengono assegnati i valori iniziali alle variabili e si inseriscono le coordinate della casella (0, 0) nel primo nodo dell'albero:

Si entra in un ciclo in cui, per tutti i nodi di uno stesso livello, si calcolano le coordinate delle caselle adiacenti. Se queste contengono un asterisco e non sono già presenti nell'albero, si depositano le loro coordinate sullo stack:

Quando termina il ciclo si prelevano, contandoli, tutti i nodi depositati sullo stack e li si inseriscono nell'albero:

Infine si deve incrementare il puntatore all'albero del numero di nodi successori e si deve ripetere il ciclo se non si è raggiunta la casella terminale.

A questo punto per determinare il numero di passi minimo si deve risalire l'albero: