// PRINCIPAL
# include <stdio.h>
# include <stdlib.h>
# include "lablib.h"
# include "pilhalib.h"
       	      
int main()
{
 struct pilha *caminho;
 struct tabuleiro lab;
 struct tabuleiro *l;
 l=&lab;
 
 inicia_tabuleiro(l);
 imprime_tabuleiro(l);
 
 cria_pilha(caminho);
 
 acha_caminho(caminho, l);
 
 libera_pilha(caminho);
   
 return 0;
}
// FIM PRINCIPAL

// LABLIB.C
# include <stdio.h>
# include <stdlib.h>
# include "lablib.h"
# include "pilhalib.h"

void imprime_tabuleiro (struct tabuleiro *t)
{
 int i, j;
 
 printf("Labirinto:\n");
 for (i=0; i<t->m_lin; i++)
    {
     for (j=0; j<t->n_col; j++)
        printf("%c ", t->mat[i][j]);
     printf("\n");
    }
}

void inicia_tabuleiro (struct tabuleiro *t)
{
 char nome_arq[25];
 FILE *arq;
 char ch;
 int i,j;
 
 	/* Abre arquivo para leitura */
 printf("Digite o nome do arquivo a ser aberto:\n");
 scanf("%s", nome_arq);
 
 arq = fopen(nome_arq,"r");

 if(arq == NULL)
   {
    printf("Arquivo não existente. Saindo...\n");
    exit(1);	   
   }   
     
 /* Le labirinto do arquivo */       
 i=0;
 while ((ch=fgetc(arq)) != EOF)
      {
       j=0;
       while ((ch=fgetc(arq)) != '\n')
            { 
             if ((ch != '\n'))
               t->mat[i][j]=ch;
             j++;
            }
       i++;
      } 
 
 /* Captura a ordem da matriz (MxN) */
 t->m_lin=i;
 t->n_col=j;
 
 /* Entrada e saida do labirinto */
 t->entrada.x=1;
 t->entrada.y=0;
 t->saida.x= t->m_lin-2;
 t->saida.y= t->n_col-1;
 
 /* Testa validade da entrada e da saida */
 if ((t->mat[t->entrada.x][t->entrada.y] == 'X') || (t->mat[t->saida.x][t->saida.y]) == 'X')
  {
   printf("Entrada de dados inconsistente. Abortando...\n");
   exit(1);
  }
}

struct pilha *acha_caminho (struct pilha *topo, struct tabuleiro *t)
{
 struct coordenada *atual= (struct coordenada *) malloc (sizeof(atual));
 int aleat=0;
 
 atual->x= t->saida.x;
 atual->y= t->saida.y;
 
 do {
     switch (decide_direcao(t, atual->x, atual->y, aleat))
        {
         case 1: topo=empilha(topo, atual->x, atual->y);	// empilha
                 t->mat[atual->x][atual->y]= '.';	// marca
                 atual->x--; 				// anda p/ cima
                 aleat=0;
                 break;
         case 2: topo=empilha(topo, atual->x, atual->y);	// empilha
                 t->mat[atual->x][atual->y]= '.';	// marca
                 atual->y--; 				// anda p/ esquerda
                 aleat=0;
                 break;        
         case 3: topo=empilha(topo, atual->x, atual->y);	// empilha
                 t->mat[atual->x][atual->y]= '.';	// marca
                 atual->x++; 				// anda p/ baixo
                 aleat=0;
                 break;
         case 4: topo=empilha(topo, atual->x, atual->y);	// empilha
                 t->mat[atual->x][atual->y]= '.';	// marca
                 atual->y++; 				// anda p/ direita
                 aleat=0;
                 break;
////////////////////////////////////////////////////////////////////////                 
         case -1: t->mat[atual->x][atual->y]= 'X';	// marca anterior
                  atual->x--; 				// anda p/ cima
                  aleat=1;
                  break;
         case -2: t->mat[atual->x][atual->y]= 'X';	// marca anterior
                  atual->y--; 				// anda p/ esquerda
                  aleat=1;
                  break;        
         case -3: t->mat[atual->x][atual->y]= 'X';	// marca anterior
                  atual->x++; 				// anda p/ baixo
                  aleat=1;
                  break;
         case -4: t->mat[atual->x][atual->y]= 'X';	// marca anterior
                  atual->y++; 				// anda p/ direita
                  aleat=1;
                  break;        
////////////////////////////////////////////////////////////////////////                 
        }
   
    } while ((atual->x != t->entrada.x) || (atual->y != t->entrada.y));
    usleep(999999);			 // delete esta linha (TEST_LINE)
    imprime_tabuleiro(t); 			 // delete esta linha (TEST_LINE)
    imprime_caminho(topo); 			 // delete esta linha (TEST_LINE)
}

int decide_direcao(struct tabuleiro *t, int lin, int col, int chave)
{
	// acima
 if (t->mat[lin-1][col] == ' ')
   return 1;
   	// esquerda
 if (t->mat[lin][col-1] == ' ') 
  return 2;
 	// abaixo
 if (t->mat[lin+1][col] == ' ') 
  return 3;
   	// direita
 if (t->mat[lin][col+1] == ' ') 
  return 4;
////////////////////////////////////
 	// acima
 if (t->mat[lin-1][col] == '.')
   return -1;
   	// esquerda
 if (t->mat[lin][col-1] == '.') 
  return -2;
 	// abaixo
 if (t->mat[lin+1][col] == '.') 
  return -3;
   	// direita
 if (t->mat[lin][col+1] == '.') 
  return -4;
 if (chave == 1)
   {
    srand((unsigned)time(NULL));
    return (rand()%4) + 1;
   }
////////////////////////////////////  
}

void imprime_caminho (struct pilha *topo)
{
 struct coordenada *coord= (struct coordenada *) malloc (sizeof(coord));

 while (!(pilha_vazia(topo)))
      {
       coord=desempilha(topo, coord);
       printf("(%d,%d)\n", coord->x, coord->y);
       usleep(99999);			 // delete esta linha (TEST_LINE)
      }
}
// FIM LABLIB.C

// LABLIB.H

#define MAX_LIN 100
#define MAX_COL 100

struct coordenada {
                   int x, y;
                  };        	      
        	      
struct tabuleiro {
		  char mat[MAX_LIN][MAX_COL];	// matriz
		  int m_lin, n_col;		// tamanho da matriz (MxN)
		  struct coordenada entrada;	// coordenadas da entrada
		  struct coordenada saida;	// coordenadas da saida
                 };
                 
void inicia_tabuleiro (struct tabuleiro *);
void imprime_tabuleiro (struct tabuleiro *);
struct pilha *acha_caminho (struct pilha *, struct tabuleiro *);
int decide_direcao (struct tabuleiro *, int , int , int);
void imprime_caminho (struct pilha *);
// FIM LABLIB.H

// PILHALIB.C
# include <stdio.h>
# include <stdlib.h>
# include "lablib.h"
# include "pilhalib.h"

void cria_pilha (struct pilha *topo)
{
 topo=(struct pilha *) malloc(sizeof(struct pilha));
 topo = NULL;
}

void libera_pilha (struct pilha *topo)
{
 struct pilha *p= (struct pilha *) malloc(sizeof(struct pilha));
 
 while (!(pilha_vazia(topo)))
      {
       p=topo;
       topo=topo->prox;
       free(p);
      }
  free(topo);
}

int pilha_vazia (struct pilha *topo)
{
 if (topo == NULL)
   return 1;
 return 0;
}

int pilha_cheia (struct pilha *topo)
{
 topo = (struct pilha *) malloc (sizeof(topo));
 if (topo == NULL)
   return 1;
 return 0;
}

struct pilha *empilha (struct pilha *topo, int lin, int col)
{
 struct pilha *p = (struct pilha *) malloc (sizeof(p));

 if (pilha_cheia(topo))
   {
    printf("Pilha cheia!!\n");
    free(p);
    exit(1);
   }
 else
   {
    cria_pilha(p); 
    p->pos.x= lin;
    p->pos.y= col;
    if (pilha_vazia(topo))
      topo = p;
    else
      p->prox= topo->prox;
    topo->prox=p;
   }  
  printf("empilhou: %d %d\n", p->pos.x, p->pos.y); // delete esta linha (TEST_LINE)
  return topo;
}

struct coordenada *desempilha (struct pilha *topo, struct coordenada *pos)
{
 struct pilha *p= (struct pilha *) malloc (sizeof(p));
 
 if (pilha_vazia(topo))
   {
    printf("Pilha vazia!!\n");
    exit(1);
   }
 pos->x=topo->pos.x;
 pos->y=topo->pos.y;
 printf("tinha %d %d\nDESempilhou: %d %d\n", pos->x, pos->y, topo->pos.x, topo->pos.y); // delete esta linha (TEST_LINE)
 p=topo;
 topo=topo->prox;
 free(p);
 return pos;
}
// FIM PILHALIB.C

// PILHALIB.H

struct pilha {
	      struct coordenada pos;
	      struct pilha *prox;
	     } topo; 
	     
void cria_pilha (struct pilha *);
void libera_pilha (struct pilha *);
int pilha_cheia (struct pilha *);
int pilha_vazia (struct pilha *);
struct pilha *empilha (struct pilha *, int , int);
struct coordenada *desempilha (struct pilha *, struct coordenada *);

// FIM PILHALIB.H