Nombre Password [ Regístrate ]

Caminos (OIE 1 - 1997) - Código en C
#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.
 }


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