Nombre Password [ Regístrate ]

Caminos (OIE 1 - 1997) - Solución

 

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



© (2001-2008) ALGORITMIA.NET - Política de privacidad