#include<stdio.h>
#include<string.h>
char busca(char,char,char); // Funci¢n recursiva que
// busca la palabra pedida en la tabla.
char mapa[9][9]; // Variable que contiene la tabla.
char v[9][9]; // Indica si hemos utilizado una casilla o no.
char F,C; // N£mero de filas y columnas de la tabla.
char cad[100],l; // Palabra a buscar y su longitud.
char ff[8]={1,1,1,-1,-1,-1,0,0}; // Incremento de la fila
char cc[8]={-1,0,1,-1,0,1,-1,1}; // Incremento de la columna
int main()
{
char a,b;
freopen("cami.dat","r",stdin); // Abro los ficheros.
freopen("cami.out","w",stdout);
scanf(" %d %d",&F,&C); // Leo el n£mero de filas y columnas.
for(a=0;a<F;a++) // Leo la tabla.
for(b=0;b<C;b++)
scanf(" %c",&mapa[a][b]);
scanf(" %s",&cad); // Leo la palabra a buscar
l=strlen(cad); // y su longitud.
memset(v,0,sizeof(v)); // No he utilizado ninguna casilla.
for(a=0;a<F;a++) // Recorro la tabla buscando la £ltima letra de la palabra
for(b=0;b<C;b++)
if(mapa[a][b]==cad[l-1]) // Cuando la encuentro
{
v[a][b]=1; // Marco como utilizada la casilla.
if(busca(a,b,l-2)) // Y busco la pen£ltima. Si forma parte de la palabra:
printf("%d %d\n",a+1,b+1); // Imprimo la posici¢n de esa casilla.
v[a][b]=0; // Marco como no utilizada la casilla.
}
return(0); // Fin.
}
// Funci¢n recursiva que busca la palabra en la tabla, del final al principio,
// para que al imprimir las casillas est‚n ordenadas de principio a fin.
char busca(char f,char c,char prof)
{
char a,f1,c1;
if(prof<0) // Si se ha encontrado toda la palabra:
return(1); // Empezar a deshacer el camino.
for(a=0;a<8;a++) // Recorro las 8 direcciones.
{
f1=(f+ff[a]+F)%F; // Nuevo valor de la fila.
c1=(c+cc[a]+C)%C; // Nuevo valor de la columna.
if(v[f1][c1]==0 && mapa[f1][c1]==cad[prof]) // si la nueva casilla no se ha utilizado y coincide con la letra que se busca:
{
v[f1][c1]=1; // Se marca como utilizada
if(busca(f1,c1,prof-1)) // Seguir buscando con la letra anterior. Si se ha encontrado la palabra:
{
printf("%d %d\n",f1+1,c1+1); // Imprimir la casilla.
return(1); // Seguir deshaciendo el camino.
}
v[f1][c1]=0; // Se marca como no utilizada
}
}
return(0); // No se ha encontrado la palabra.
}
|