Suggerimenti [1d5]
SE
la prima lettera della matrice
(in alto a sinistra, matrice[0,0])
è diversa dalla prima lettera della parola
(parola[0])
ALLORA
siamo già sicuri di non poter individuare la parola
nella matrice
Suggerimenti [2d5]
SE
(parola[0]==matrice[0,0])
ALLORA
il problema si riduce a verificare se il resto della
parola è individuabile a partire da matrice[0,1]
(ricerca verso destra), OPPURE da matrice[1,0]
(ricerca verso il basso)
Suggerimenti [3d5]
SE
la parola è lunga un solo carattere
ALLORA
il problema diventa molto semplice
Suggerimenti [4d5]
OVVIAMENTE,
Nell'esplorare la matrice dobbiamo porre la
massima cautela nel non superare le colonne
d'Ercole, dato che la matrice possiede un
numero finito di righe e di colonne
Suggerimenti [5d5]
Dicotomia: Iterazione Vs. Ricorsione
Un approccio iterativo potrebbe
 Esplorare la matrice muovendo due indici [r,c]
 Tenere traccia delle porzioni di parola individuate
 Marcare le posizioni che non possono costituire
soluzione, o che pur potendo non la costituiscono
 Fare backtrack quando necessario
Sì ma.. la ricorsione si offre di gestire per noi, e
gratis, il meccanismo di nesting/backtracking!
L'Algoritmo [1d5]
Si tratta di una funzione ricorsiva, il cui prototipo
minimo può essere qualcosa di simile al
seguente
string f (int r, int c, string p, string o)
L'idea è che la funzione restituisca una stringa
che descrive il cammino che dalla posizione [r,c]
individua la parola p, considerando che si è già
svolto un certo cammino o per arrivare in
posizione [r,c]
L'Algoritmo [2d5]
string f (int r, int c, string p, string o)
r: indice della riga in cui iniziare la ricerca
 c: indice della colonna in cui iniziare la ricerca
 p: parola da ricercare
 o: cammino parziale percorso fino a quel
momento per giungere in posizione [r,c]

L'Algoritmo [3d5]
La prima chiamata
f(0, 0, parola, “”)
Una chiamata ricorsiva “destra”
f(r, c+1, parola+1, [?])
Una chiamata ricorsiva “basso”
f(r+1, c, parola+1, [?])
..
E questo misterioso quarto parametro?
L'Algoritmo [4d5]
Il quarto parametro è il cammino (dentro la
matrice) che via via costruiamo, e che alla fine
costituirà l'output del problema
L'idea è che ad ogni chiamata della funzione f le
venga passato il cammino attuale inteso come
testimonianza
del come si è giunti al punto [r,c]
L'Algoritmo [5d5]
La funzione valuterà se da quel punto una
soluzione è impossibile (e in caso restituirà il
valore ASSENTE), altrimenti arricchirà il cammino
passato della mossa del caso, e restituirà il tutto
come risultato della funzione
Il susseguirsi delle chiamate ricorsive
nell'inevitabilmente giusto ordine costruirà il
cammino (se il cammino esiste, altrimenti sarà
restituito ASSENTE)
I dettagli [1d4]
In pieno spirito OII
non eseguiamo alcun controllo di validità
sui dati di ingresso
semplicemente, assumiamo siano corretti ;-)
I dettagli [2d4]
Si noti che dal file di input leggiamo
stringhe di testo (riga per riga),
che però poi disponiamo in una matrice quadrata
di caratteri
I dettagli [3d4]
Abbiamo scelto di utilizzare la “A” come carattere
di output, oltre a “D” (destra) e “B” (basso)
“A” sta per “assente”, e ricevere dalla funzione f
una “A” come esito indica che quella
sottoricerca è fallita
I dettagli [4d4]
Estendiamo la libreria di input/output
string leggiStringa(void) {
string x;
in >> x;
return x;
}
void scriviStringa(string x) {
out << x;
}