Este problema se ha resuelto utilizando la recursividad (marcha atrás, backtracking). Primero se busca
la primera letra de la palabra buscada, y una vez encontrada se busca la siguiente entre
las adyacentes. Así se miran todas las posibilidades hasta que se encuentra la palabra buscada.
Es un método de fuerza bruta, un poco lento para casos grandes, pero muy efectivo cuando el
tamaño de la tabla es pequeño (el límite en este problema es 9). El problema en sí no tiene
más dificultades, pero se pueden utilizar un par de trucos para hacer el código más sencillo:
1.- No está permitido recorrer dos veces la misma casilla en una palabra, por
lo que hay que tener algo que nos indique si una casilla se ha utilizado anteriormente o no. Para
eso se utiliza otra tabla auxiliar del mismo tamaño que la original, inicializada a 0. Cuando una casilla
se utiliza, la casilla correspondiente de la tabla auxiliar pasa a marcar 1, así cuando se
vaya a utilizar una casilla primero habrá que mirar si ya se ha usado o no (marca 1 ó 0). Hay
que tener cuidado, al hacer backtracking hay que volver a poner la casilla a 0.
2.- Para mirar las casillas adyacentes en busca de una nueva letra se puede
implementar una a una las 8 direcciones, lo que haría un código largo, engorroso y difícil de
depurar, o se puede tener en dos arrays los incrementos posibles de sila y de columna; si
estamos en (F,C), podemos ir a (F-1,C-1), (F-1,C), (F-1,C+1), (F,C-1), (F,C+1), (F+1,C-1),
(F+1,C) y (F+1,C+1). Si tenemos un array con los valores:
FF={-1,-1,-1, 0, 0, 1, 1, 1};
CC={-1, 0, 1,-1, 1,-1, 0, 1};
se puede llegar a las 8 casillas con un bucle for, del tipo:
for(i=0;i<8;i++)
{
filanueva = filaantigua + FF[i];
columnanueva = columnaantigua + CC[i];
...
}
Así se ahorra líneas de código, y en caso de haber errores, con modificarlo en un
sitio basta.
3.- El problema también considera adyacentes de una casilla situada en un borde
las casillas del lado opuesto, como si la tabla fuera cíclica. Para no tener que preocuparse de
este problema, al hallar las casillas adyacentes basta con hacerlas módulo número de filas (o
columnas, según corresponda):
filanueva = (filaantigua + FF[i]) % numerodefilas;
columnanueva = (columnaantigua + CC[i]) % numerodecolumnas;
Pero esto falla en un caso, cuando filaantigua es 0, y FF[i] es -1, filanueva
toma el valor -1 (lo que daría un runtime error). Para evitar eso, y aprovechándonos de que
a % b = (a + b) % b, basta con poner:
filanueva = (filaantigua + FF[i] + numerodefilas) % numerodefilas;
columnanueva = (columnaantigua + CC[i] + numerodecolumnas) % numerodecolumnas;
Así nos aseguramos de que las nuevas coordenadas son positivas.
4.- El programa te pide que des las posiciones de las casillas en las que está la palabra,
ordenadas del principio al final, y al hacer backtracking salen ordenadas justo al revés (del final al
principio). Para dar la salida correctamente hay dos soluciones: una es guardar las casillas en una tabla,
lo que supone un gasto de memoria (y de tiempo, importante en una función recursiva). Lo más eficaz es buscar
la palabra del final al principio, en vez de buscarla del principio al final. Por ejemplo, si te piden
hallar la palabra SOLA, hallamos la palabra ALOS, y al dar las coordenadas de esta palabra al revés,
se obtienen las coordenadas de la palabra SOLA en orden correcto.
Temas relacionados
Backtracking Código Código fuente en C |
