[JAVA] Avete un'idea come risolvere questo problema?

[luxorl]

Allora, mi sono trovato davanti una traccia che chiede di implementare un package puzzle, che prende da file un insieme di lettere messe stile matrice:

Esempio:


A C P A S
A P O C S
F R E W A
C O P E O
S L I W Q


E poi prende sempre da file un "dizionario", che contiente una lista di parole.

Un metodo risolvi() accetta una parola del dizionario e deve cercarla nella matrice di lettere a partire da tutte le posizione e verso tutte le direzioni (Una sorta del classico giochino da settimana enigmistica) ...questo metodo risolvi() dovrebbe una volta trovata la parola, restituirla unita alle cordinate della lettera di partenza e alla direzione in cui questa parola si estende.

Esempio:


A C P A S
A P O C S
F R E W A
C O P E O
S L I W Q

E' presente la parola APE a partire dalla coordinata <0,0> e si estende verso SUD-EST...


In pratica il mio problema è proprio questo maledetto metodo risolvi()!! Come diavolo potrei farlo?

Grazie in anticipo a chiunque vorrà darmi una mano :mano:

[niko0]

quesito molto interessante!

...ci penso e se mi viene qualche idea... mi faccio vivo :cool:

come memorizzi la matrice di lettere?

[fgmac]

Un'idea potrebbe essere quella di spezzare il problema in due passi.
Nel primo passo identifichi le sole direzioni utili in base alla lunghezza della parola da cercare :
nell'esempio che facevi, per la posizione 0,0 le direzioni utili sono solo tre: sud, sud-est, est

Fatto questo metodo iterativo sulle lettere.

questa e' la prima idea che mi e' venuta in mente. :rolleyes:

ciao,

[end.is.forever]

public Vector <Parola> risolvi(Matrice <char> matrice)
{
Vector <Parola> paroleTrovate = new Vector <Parola>();
for (int r = 0; r < matrice.numeroRighe(); r++)
for (int c = 0; c < matrice.numeroColonne(); c++)
{
if (r < matrice.numeroRighe())
{
paroleTrovate.addRange(cercaInDirezione(matrice, r, c, EST));
if (c < matrice.numeroColonne())
paroleTrovate.addRange(cercaInDirezione(matrice, r, c, SUD_EST));
if (c > 0)
paroleTrovate.addRange(cercaInDirezione(matrice, r, c, NORD_EST));
}
... uguale per le altre direzioni
}
return paroleTrovate;
}

private Vector <Parola> cercaInDirezione(int r, int c, Direzione d)
{
Vector <Parola> paroleProvate = new Vector <Parola>();
int numLettere;
switch (d)
{
case EST: numMaxLettere = matrice.numeroColonne() - c;break;
case SUD_EST:
int maxC = matrice.numeroColonne() - c;
int maxR = matrice.numeroRighe() - r;
numMaxLettere = min(maxC, maxR);
break;
..uguale per le altre direzioni
}
for (int numLettere = 2; numLettere < numMaxLettere; numLettere++)
{
char[] parolaDaProvare = new char[numLettere];
for (int i = 0, ri = r; ci = c; i < numLettere; i++)
{
parolaDaProvare[i] = matrice.get(ri, ci);
switch (d)
{
case EST: ci++;break;
case SUD_EST: ci++;ri++;break;
..uguale per le altre direzioni
}
}
Parola parola = Dizionario.cercaParola(parolaDaProvare);
if (parola != null)
paroleTrovate.add(parola);
}
return paroleTrovate;
}


Non ho compilato, ma in linea di massima farei così; una prima ottimizzazione potrebbe essere di considerare solo 4 delle 8 direzioni e poi al momento di testare la parola provarla in entrambi i sensi.