Solución a "Boggle" 100pts. Preselectivo 2015 - Etapa 1 - Problemset #8

boggle.cpp

#include <stdio.h>
#include <string.h>
#define TABLERO 4
/*
	Program: Boggle
	Encoded by Michael Serrato.
*/
int N; 
char tablero[5][5]; 
int mapa[5][5] = {0}; /* Mapa: Sirve como auxiliar 
							   para marcar las casillas
							   por las que ya se ha pasado.
							   
							   NOTA: Es necesario inicializar la matriz
							   en 0. */

char diccionario[101][17]; /* Diccionario de Palabras */

					//	3  4  5  6  7   8 o más...
int calif[] = {0, 0, 0, 1, 1, 2, 3, 5, 11};

typedef struct coord
{
	int x, y;
} Coord;


Coord coord[101]; /* Coord: En este arreglo almacenaremos
							las coordenadas donde podemos
							iniciar con la búsqueda de una
							determinada palabra. */

int c_size = 0;   /* c_size: Es el tamaño del vector 'Coord' */

int finish = 0; /* Indica si finalizamos la búsqueda de una determinada
					palabra. */

long long int intentos = 0; /* Variable auxiliar para conocer 
							    la complejidad y/o el tamaño que tendrá
							    nuestro árbol. */

long long int puntos = 0; /* Variable global que almacena el total de
							 puntos que hemos obtenido. */

void imprimirTablero(){ /* Función auxiliar para imprimir el estado 
						   actual del tablero. */ 
int i,j;	
	printf("\n");
	for(i=0; i<TABLERO; ++i){
		printf("%s\n", tablero[i]);
	}
	printf("\n");
}

void imprimirMapa(){ /*	Función auxiliar para imprimir el estado
						actual del mapa (en otras palabras las posiciones
						por donde ya hemos pasado). */
int i,j;	
	printf("\n");
	for(i=0; i<TABLERO; ++i){
		for(j=0; j<TABLERO; ++j){
			printf("%d ", mapa[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

void imprimirDiccionario(){ /* Su única función es imprimir las 
							   palabras en el diccionario (Función Auxiliar). */
int i,j;
	printf("\n");
	for(i=0; i<N; ++i){
		printf("%s\n", diccionario[i]);
	}
	printf("\n");
}
/* Parámetros: 
(Coordenada Y, Coordenada X, Id. Palabra, Id. Letra, Longitud de la Palabra). */
void buscar(int y, int x, int palabra, int letra, int lon){
	++intentos;
	if(finish){ /* Si la variable global 'finish' es verdadera
					entonces ya hemos terminado. */
		return;
	}
	if( y<0 || x<0 || y>=TABLERO || x>=TABLERO ){ /* Al salir del area retornamos. */
		return; 
	}
	if(letra == lon){ /* Una vez que encontremos todas las
						letras de la palabra asignamos
						1 a nuestra variable global
						para evitar continuar con la búsqueda
						y asignamos los puntos correspondientes
						a nuestra variable global 'puntos'. */
		finish = 1;
		if(lon<=8){ 
			puntos += calif[lon];
		}else { // Si la longitud es mayor que 8 agregamos 11 puntos
			puntos += 11; 
		}
		return;
	}
	if(mapa[y][x]){ /* Retornamos sólo si
						mapa[y][x] esta marcada. */
		return;
	}
	if(tablero[y][x] != diccionario[palabra][letra]){ /* Retornar sólo si la letra del tablero
														 no es igual a la que buscamos. */
		return;
	} else {
		mapa[y][x] = 1;
		buscar(y-1, x, palabra, letra+1, lon); // Arriba
		buscar(y-1, x+1, palabra, letra+1, lon); // Diagonal Arriba/Dercha
		buscar(y, x+1, palabra, letra+1, lon); // Derecha
		buscar(y+1, x+1, palabra, letra+1, lon); // Diagonal Abajo/Derecha
		buscar(y+1, x, palabra, letra+1, lon); // Abajo
		buscar(y+1, x-1, palabra, letra+1, lon); // Diagonal Abajo/Izquierda
		buscar(y, x-1, palabra, letra+1, lon); // Izquierda
		buscar(y-1, x-1, palabra, letra+1, lon); // Diagonal Arriba/Izquierda
		mapa[y][x] = 0;
	}
}

void puntosEncontrados(char c){ /* Encontrar los posibles puntos
								   en donde podemos iniciar nuestra búsqueda.
								   Estos puntos son almacenados en el arreglo 'Coord'.  */
int i,j;
	for(i=0; i<TABLERO; ++i){
		for(j=0; j<TABLERO; ++j){
			if(tablero[i][j] == c){
				coord[c_size].y = i;
				coord[c_size++].x = j;
			}
		}
	}
}

void vaciarPuntos(){ /* Vacia las coordenadas del arreglo 'Coord'. */
int i,j;
	while(--c_size >= 0){
		coord[c_size].x = 0;
		coord[c_size].y = 0;
	}
}

void palabra(int indice){
int i,j;
	finish = 0;
	intentos = 0;
	c_size = 0;
	puntosEncontrados(diccionario[indice][0]); 
	for(i=0; i<c_size; ++i){
		buscar(coord[i].y,coord[i].x, indice, 0, strlen(diccionario[indice])); /* Iniciamos con nuestra búsqueda
																			      en las coordenadas asignadas. */
		if(finish){ // Si finish es igual a verdadero
			break; 	// Terminamos la búsqueda.
		}
	}
	vaciarPuntos(); // Vaciamos las coordenadas del arreglo 'Coord'.
}

int main(){
	int i,j;
	for(i=0; i<TABLERO; ++i){
		scanf("%s",tablero[i]);
	}
	scanf("%d",&N);
	for(i=0; i<N; ++i){
		scanf("%s",diccionario[i]);
	}
	for(i=0; i<N; ++i){ // Buscamos todas las palabras de diccionario
		palabra(i);
	}
	printf("%lld\n", puntos); /* Finalmente imprimimos el total de puntos 
								 obtenidos.*/
	return 0;
}