[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

[niko0]

quesito molto interessante!

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

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.

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.