/*
Alunos: Mateus Mendelson Esteves da Silva e Amadeu Medina Borges
Matrículas: 11/0017579 e 10/0024157
Data de entrega: 06/11/2011
Estruturas de Dados, Turma E, Professor Díbio, 2º/2011
*/
#include <stdlib.h>
#include <stdio.h>
/* Estruturas */
struct no{ //Estrutura para a árvore genérica (nó)
int info;
int lin;//Indica a linha no tabuleiro
int col;//Indica a coluna no tabuleiro
struct no *cima;//quadrado de cima
struct no *baixo;//quadrado de baixo
struct no *direita;//quadrado da direita
struct no *esquerda;//quadrado da esquerda no tabuleiro
};
typedef struct no No;//No quer dizer Nó
////////////////////////////////
/* Protótipos das funções */
void libera_tabuleiro(int **, int);
void imprime_tabuleiro(int **, int);
void preenche_arvore_de_possibilidades(No *, int **, int, int *);
No *cria_no(int, int, int, No *, No *, No *, No *);
void libera_arvore_de_jogos(No *);
int buscar_o_no_final(No *, int , int **, int);
///////////////////////////////////////////////////////////
/* Função principal */
int main(){
FILE *fonte, *resultado;
int **tabuleiro;//'Alterar' indicará as posições que podem ser alteradas com 0. As que não podem, com 1
int x = 0;
int *confirmacao = &x;//Confirma se o tabuleiro tem solução( 0 quer dizer sem solução; != 0 significa tem solução
int N, i, j;
int ii = -1, ji = -1; //Posição incial, ou seja, coordenada do número 1. (ii = linha incial; ji = coluna inicial)
No *r;//Raíz da árvore genérica (árvore de jogo). Ela será formada por todas as possibilidades de jogo.
fonte = fopen("entradaProj4.txt", "r");
if(fonte == NULL){
printf("Arquivo fonte nao encontrado!\n\n");
//system("PAUSE");
exit(1);
}
fscanf(fonte, "%d", &N);
if(N < 6 || N > 10){
printf("\n\nErro! O arquivo de entrada designa um tabuleiro ");
if(N <= 6){
printf("menor do que o minimo permitido!\n\n");
}else{
printf("maior do que o maximo permitido!\n\n");
}
fclose(fonte);//Fechando o arquivo fonte
//system("PAUSE");
exit(2);
}
//Iniciando e preenchendo o tabuleiro
tabuleiro = (int **) malloc(N*sizeof(int));
for(i = 0; i < N; i++){
tabuleiro[i] = (int *) malloc(N*sizeof(int));
}
//Preenchendo o tabuleiro
for(i = 0; i < N; i++){
for(j = 0; j < N; j++){
fscanf(fonte, "%d", &tabuleiro[i][j]);
}
}
//Fechando o arquivo fonte
fclose(fonte);
//Imprimindo o tabuleiro inicial
printf("Tabuleiro inicial:\n\n");
imprime_tabuleiro(tabuleiro, N);
printf("\n");
//Buscando a posição inicial
for(i = 0; i < N; i++){
for(j = 0; j < N; j++){
if(tabuleiro[i][j] == 1){
ii = i;
ji = j;
}
}
}
if(ii == -1){
printf("\n\nErro! O tabuleiro nao possue posicao inicial! Encerrado!\n\n");
//system("PAUSE");
exit(3);
}
r = cria_no(1, ii, ji, NULL, NULL, NULL, NULL);//Criando a raiz da árvore
preenche_arvore_de_possibilidades(r, tabuleiro, N, confirmacao);//Preenche a árvore r, que se refere à jogadas de "tabuleiro" que possui N*N posições
if(*confirmacao == 0){
printf("\nO tabuleiro nao possui solucao!\n\n");
//Liberando estruturas
libera_arvore_de_jogos(r);
libera_tabuleiro(tabuleiro, N);
free(confirmacao);
//system("PAUSE");
exit(4);
}
x = buscar_o_no_final(r, N, tabuleiro, 0);
//Imprimindo a solução do tabuleiro
printf("\nSolução:\n\n");
imprime_tabuleiro(tabuleiro, N);
printf("\n");
//Salvando a solução no arquivo de texto
resultado = fopen("solucaoProj4.txt", "w");//Criando o arquivo
for(i = 0; i < N; i++){
for(j = 0; j < N; j++){
fprintf(resultado, "%d ", tabuleiro[i][j]);
}
printf("\n");
}
//Fechando o arquivo
fclose(resultado);
//Liberando estruturas
libera_arvore_de_jogos(r);
libera_tabuleiro(tabuleiro, N);
free(confirmacao);
//system("PAUSE");
return 0;
}
////////////////////////////////////////////////////////////////
//Corpo das funções
//Função que imprime o tabuleiro
void imprime_tabuleiro(int **tabuleiro, int t){
int i, j;
for(i = 0; i < t; i++){
for(j = 0; j < t; j++){
printf("%d ", tabuleiro[i][j]);
}
printf("\n");
}
}
//Função que libera o tabuleiro
void libera_tabuleiro(int **p, int t){
int i;
for(i = 0; i < t; i++){
free(p[i]); //Liberando as linhas da matriz
}
free(p); //Liberando a matriz
}
//Função que libera a árvore de jogo
void libera_arvore_de_jogos(No *arvore_jogo){
No *p = arvore_jogo;
if(p->cima == NULL && p->baixo == NULL && p->direita == NULL && p->esquerda == NULL){
free(p);
}else if(p->cima != NULL){
libera_arvore_de_jogos(p->cima);
}else if(p->baixo != NULL){
libera_arvore_de_jogos(p->baixo);
}else if(p->direita != NULL){
libera_arvore_de_jogos(p->direita);
}else if(p->esquerda != NULL){
libera_arvore_de_jogos(p->esquerda);
}
}
void preenche_arvore_de_possibilidades(No *r, int **tabuleiro, int N, int *confirmacao){ //Já que a posição inicial já é fornecida (de acordo com o roteiro do projeto) não nos preocuparemos com os casos em que o tabuleiro inicial não possui o número 1 (que é a posição inicial)
int i = r->lin, j = r->col;
int apoio;
int x;
if(r->info == N*N){
x = r->info;//Checagem para saber se o último número foi colocado no tabuleiro, ou seja, se há solução
*confirmacao = x;
}
if(r->info < N*N && r != NULL){//Checa se já preenchemos a árvore com todos os números e se o nó é um nó terminal (ou inválido)
if((j + 1 < N) && tabuleiro[i][j + 1] == 0 || tabuleiro[i][j + 1] == (r->info) + 1){
r->direita = cria_no((r->info) + 1 /* número seguinte no tabuleiro */, i, j + 1, NULL, NULL, NULL, NULL);
apoio = tabuleiro[i][j + 1];//Armazenamos o valor inicial nessa coordenada
tabuleiro[i][j + 1] = (r->info) + 1;//Alteramos temporariamente o valor nessa coordenada, para evitar que utilizemos duas vezes o mesmo quadrado na montagem da árvore
//printf("\n%d\t%d\t%d\n", r->info, r->lin, r->col);
//system("PAUSE");
preenche_arvore_de_possibilidades(r->direita, tabuleiro, N, confirmacao);
tabuleiro[i][j + 1] = apoio;//Recolocamos o valor original na posição do tabuleiro, para que nada seja alterado ao final
}
if((j - 1 >= 0) && (tabuleiro[i][j - 1] == 0 || tabuleiro[i][j - 1] == (r->info) + 1)){
if(j + 1 < N && tabuleiro[i][j + 1] == (r->info) + 1){//Só há um caminho possível
}else{
r->esquerda = cria_no((r->info) + 1 /* número seguinte no tabuleiro */, i, j - 1, NULL, NULL, NULL, NULL);
apoio = tabuleiro[i][j - 1];//Armazenamos o valor inicial nessa coordenada coordenada
tabuleiro[i][j - 1] = (r->info) + 1;//Alteramos temporariamente o valor nessa coordenada, para evitar que utilizemos duas vezes o mesmo quadrado na montagem da árvore
//printf("\n%d\t%d\t%d\n", r->info, r->lin, r->col);
//system("PAUSE");
preenche_arvore_de_possibilidades(r->esquerda, tabuleiro, N, confirmacao);
tabuleiro[i][j - 1] = apoio;//Recolocamos o valor original na posição do tabuleiro, para que nada seja alterado ao final
}
}
if((i + 1 < N) && (tabuleiro[i + 1][j] == 0 || tabuleiro[i + 1][j] == (r->info) + 1)){
if((j + 1 < N && tabuleiro[i][j + 1] == (r->info) + 1) || (j - 1 >= 0 && tabuleiro[i][j - 1] == (r->info) + 1)){//Só há um caminho possível
}else{
r->baixo = cria_no((r->info) + 1 /* número seguinte no tabuleiro */, i + 1, j, NULL, NULL, NULL, NULL);
apoio = tabuleiro[i + 1][j];//Armazenamos o valor inicial nessa coordenada coordenada
tabuleiro[i + 1][j] = (r->info) + 1;//Alteramos temporariamente o valor nessa coordenada, para evitar que utilizemos duas vezes o mesmo quadrado na montagem da árvore
//printf("\n%d\t%d\t%d\n", r->info, r->lin, r->col);
//system("PAUSE");
preenche_arvore_de_possibilidades(r->baixo, tabuleiro, N, confirmacao);
tabuleiro[i + 1][j] = apoio;//Recolocamos o valor original na posição do tabuleiro, para que nada seja alterado ao final
}
}
if((i - 1 >= 0) && (tabuleiro[i - 1][j] == 0 || tabuleiro[i - 1][j] == (r->info) + 1)){
if((j + 1 < N && tabuleiro[i][j + 1] == (r->info) + 1) ||(j - 1 >= 0 && tabuleiro[i][j - 1] == (r->info) + 1) || (i + 1 < N && tabuleiro[i + 1][j] == (r->info) + 1)){//Só há um caminho possível
}else{
r->cima = cria_no((r->info) + 1 /* número seguinte no tabuleiro */, i - 1, j, NULL, NULL, NULL, NULL);
apoio = tabuleiro[i - 1][j];//Armazenamos o valor inicial nessa coordenada coordenada
tabuleiro[i - 1][j] = (r->info) + 1;//Alteramos temporariamente o valor nessa coordenada, para evitar que utilizemos duas vezes o mesmo quadrado na montagem da árvore
//printf("\n%d\t%d\t%d\n", r->info, r->lin, r->col);
//system("PAUSE");
preenche_arvore_de_possibilidades(r->cima, tabuleiro, N, confirmacao);
tabuleiro[i - 1][j] = apoio;//Recolocamos o valor original na posição do tabuleiro, para que nada seja alterado ao final
}
}
//A última condição dos laços acima (if) serve para verificar se o ponto pertence ao tabuleiro
}
}
//Função que apenas cria um nó
No *cria_no(int numero /*Informação a ser armazenada no nó*/, int i/*linha da informação*/, int j /*Coluna da informaçao*/, No *Cima, No *Baixo, No *Direita, No *Esquerda){//4 últimos argumentos: indicam os nós que serão ligados ao novo nó
No *p;
p = malloc(sizeof(No)); //Criando o nó
//Preenchendo o nó com as informações
p->info = numero;
p->lin = i;
p->col = j;
p->cima = Cima;
p->baixo = Baixo;
p->direita = Direita;
p->esquerda = Esquerda;
return p; //Retornando o nó
}
//Função que busca a solução correta na árvore e preenche o tabuleiro
int buscar_o_no_final(No *r, int N, int **tabuleiro, int x){
if(x == 0){//Indica que ainda não encontramos o nó final
if((r->info != N*N) && (r != NULL)){
tabuleiro[r->lin][r->col] = r->info;
if(x == 0){
x = buscar_o_no_final(r->direita, N, tabuleiro, x);
}
if(x == 0){
x = buscar_o_no_final(r->esquerda, N, tabuleiro, x);
}
if(x == 0){
x = buscar_o_no_final(r->baixo, N, tabuleiro, x);
}
if(x == 0){
x = buscar_o_no_final(r->cima, N, tabuleiro, x);
}
}else if(r->info == N*N){
tabuleiro[r->lin][r->col] = r->info;//último elemento do tabuleiro. Encontramos o nó final!
return 1;//Opa, indicamos que o final foi encontrado e que já podemos encerrar a função!
}
}
return 1;
}
Comments