[SOLUCIONADO] ¿Alguien me puede ayudar con este ejercicio de programación en java?

[carlos12345678909]

Me gustaría saber si alguien me puede ayudar con este ejercicio de programacion
Palabras Cruzadas.

En el pasatiempo de palabras cruzadas, se dispone de una tabla de letras minúsculas NxN y el objetivo es encontrar palabras. Una palabra puede empezar en cualquier lugar en la tabla y puede ser construida utilizando letras adyacentes tanto en forma horizontal, vertical o diagonal.

Un ejemplo de una tabla 4x4 puede ser:

anap
siix
aopp
sxxx
Algunas de las palabras que aparecen son:

asas
ana
pios
Se pide construir un programa que permita tanto resolver manualmente un pasatiempo de palabras cruzadas como de forma automática. Las palabras que se buscarán no serán palabras de un diccionario sino simplemente palabras formadas por caracteres que estén en secuencia creciente respecto a su codificación en ASCII. El programa tendrá dos interfaces, uno a través de la entrada/salida estándar y el otro mediante un interfaz gráfico de usuario.

Interfaz entrada/salida estándar

Este será el interfaz por defecto y será llamado desde el método main de una clase Main del programa. No podrá haber ningún otro método main en ninguna otra clase. El objetivo del programa a través de este interfaz es resolver automáticamente un pasatiempo de palabras cruzadas como el descrito, encontrando todas las palabras diferentes válidas. Una palabra es válida si tiene de 3 a N2 letras todas ellas en orden estrictamente ascendente respecto a su codificación ASCII. Por ejemplo, "abc" es una palabra válida, "abcc" no y tampoco es legal "robar". Se debe tener en cuenta la eficiencia de la solución encontrada.

Entrada

La primera línea contendrá un número indicando el número de casos de test que siguen. A continuación irá una línea en blanco y también habrá una línea en blanco separando cada caso de test. Cada test contendrá un primer número N en una línea indicando el tamaño de la tabla. N podrá valer como mucho 20. Esa línea irá seguida de N líneas cada una de ellas con una cadena de N letras.

Salida

Para cada test la salida debe ser como se describe a continuación e ir separada con una línea en blanco, excluido el último caso de test. La salida de cada test estará formada por una lista de palabras únicas ordenadas de acuerdo a los siguientes criterios:

1. Las palabras más cortas van antes que las palabras más largas

2. Las palabras de igual longitud se ordenan lexicográficamente por su valor ASCII.

No se deben añadir blancos ni líneas extras. Si no hay palabras, no se imprimirá nada para ese test.

Ejemplo

Entrada

2

3

uno

dos

ves

4

abcd

bcda

cdab

dabc



Salida

deo
des
dev
dno
dns
dnu
dos
dou
dov
eos
eou
eov
nos
nou
nov
deos
deou
deov
dnos
dnou
dnov
abc
abd
acd
bcd
abcd

Mi duda es como plantear la función recursiva porque ya he intentado alguna pero no me sale .Espero que alguien me pueda ayudar!

[fpalomar]

Hola,

¿Puedes ponernos el algoritmo que intentas utilizar?

Saludos

[carlos12345678909]

Yo he pensado algo así
public class CalculadorDePalabras {
private ArrayList<String> listaPalabras;
private int n;
private char[][]tabla;
public CalculadorDePalabras(int n, char[][]tabla){
this.n=n;
this.tabla=tabla;
}
public int movimientos(int i, int j,int indice){

return 0;
}
public void comprobarCamino(int i, int j, int dir, String palabra, int n)
{
int sig_i=0 ,sig_j=0;

// Calculamos la posicion del siguiente elemento en funcion de la posicion
switch(dir)
{
case 1: // Arriba
sig_i = i;
sig_j = j-1;
break;
case 2: // Diagonal arriba derecha
sig_i = i+1;
sig_j = j-1;
break;
case 3: // derecha
sig_i = i+1;
sig_j = j;
break;
case 4: // Diagonal abajo derecha
sig_i = i+1;
sig_j = j+1;
break;
case 5: // Abajo
sig_i = i;
sig_j = j+1;
break;
case 6: // Diagonal abajo izquierda
sig_i = i-1;
sig_j = j+1;
break;
case 7: // izquiera
sig_i = i-1;
sig_j = j;
break;
case 8: // Diagonal arriba izquierda
sig_i = i-1;
sig_j = j-1;
break;
}

if ( ((sig_i >= 0 && sig_i < this.n) && (sig_j >= 0 && sig_j < this.n)))
{

// Existe siguiente elemento
if ((int)this.tabla[i][j]< (int)this.tabla[sig_i] [sig_j]){


// Correcto
palabra = palabra + this.tabla[sig_i][ sig_j];
System.out.println(palabra);
comprobarCamino(sig_i, sig_j, dir, palabra, n);
}
else
{
if (palabra.length() >= 3)
{
// Palabra correcta
listaPalabras.add(palabra);
System.out.println(palabra);
}
}



}}


public ArrayList<String> getListaPalabras() {
return listaPalabras;
}


}

[fpalomar]

Hola,

Pues la verdad, no es que sea de juegos pero por lo que he visto es como la sopa de letras ¿no?. Pero no entiendo mucho las instrucciones, yo lo veo así:

1. Definir las dimensiones del tablero
2. Si las dimensiones son N=4 , 4 es el máximo para cada palabra, pero puede haber de 3, 2, 1
aquí se aplicaria el factorial.
3. Supongo que según estas dimensiones se debería aplicar:
- X palabras de 4
- X palabras de 3
- X palabras de 2
- X palabras de 1

Si te han indicado que debes utilizar funciones recursivas no te puedo ayudar mucho porque apenas las he visto.

Saludos