/* 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);
   
 return 0;
}
// FIM PRINCIPAL

//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 *);
void imprime_caminho (struct pilha *);
int decide_direcao (struct tabuleiro *, int , int );
// FIM LABLIB.H

// 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;
}


struct pilha *acha_caminho (struct pilha *topo, struct tabuleiro *t)
{
 struct coordenada atual;
 
 atual.x= t->entrada.x;
 atual.y= t->entrada.y;

	/* Verifica entrada do labirinto */ 
 if (t->mat[atual.x][atual.y] == ' ')
    empilha(topo, atual.x, atual.y);
 else
     {
      printf("Entrada de dados inconsistente.\nA entrada do labirinto deve ser em (1,0).\n");
      exit(1);
     }
     
 do {
 /*
     if (t->mat[atual.x][atual.y] == ' ')
       {  printf("Empilhou %d %d\n",atual.x, atual.y );}
     else
       { desempilha(topo); printf("DESempilhou %d %d\n",atual.x, atual.y); } */
     switch (decide_direcao(t, atual.x, atual.y))
          {
           case 1: empilha(topo, atual.x, atual.y); atual.x++; break;	// para baixo
           case 2: empilha(topo, atual.x, atual.y); atual.y++; break;	// para direita
           case 3: empilha(topo, atual.x, atual.y); atual.x--; break;	// para cima
           case 4: empilha(topo, atual.x, atual.y); atual.y--; break;	// para esquerda
           case -1: break;
           case -2: break;
           case -3: break;
           case -4: break;
           case 0: break;
           default: break;
          }
    } while ((atual.x != t->saida.x) || (atual.y != t->saida.y));
 
 imprime_caminho(topo);
}

void imprime_caminho (struct pilha *topo)
{
 if (pilha_vazia(topo))
   printf("Naum ha conexao entre os pontos de entrada e saida do labirinto.\n");
 else
    {
     struct pilha *p=topo;
     do {
           printf("(%d,%d) ",p->pos.x, p->pos.y);
           p=p->prox;
        }  while (p->prox != NULL);
    }
}

int decide_direcao (struct tabuleiro *t, int lin, int col)
{
 	// para baixo
 if (t->mat[lin+1][col] == ' ')
  return 1;
	// para direita
 if (t->mat[lin][col+1] == ' ')
  return 2;
	// para cima
 if (t->mat[lin-1][col] == ' ')
  return 3;
	// para esquerda
 if (t->mat[lin][col-1] == ' ')
  return 4;
	// soh vai pra baixo
 if ((t->mat[lin+1][col] == ' ') && (t->mat[lin][col+1] != ' ') && (t->mat[lin-1][col] != ' ') &&  (t->mat[lin][col-1] != ' '))
  return -1;
  	// soh vai pra direita
 if ((t->mat[lin+1][col] != ' ') && (t->mat[lin][col+1] == ' ') && (t->mat[lin-1][col] != ' ') &&  (t->mat[lin][col-1] != ' '))
  return -2;
  	// soh vai pra cima
 if ((t->mat[lin+1][col] != ' ') && (t->mat[lin][col+1] != ' ') && (t->mat[lin-1][col] == ' ') &&  (t->mat[lin][col-1] != ' '))
  return -3;
	// soh vai pra esquerda
 if ((t->mat[lin+1][col] != ' ') && (t->mat[lin][col+1] != ' ') && (t->mat[lin-1][col] != ' ') &&  (t->mat[lin][col-1] == ' '))
  return -4;
  	// nao vai a lugar nenhum
  if ((t->mat[lin+1][col] != ' ') && (t->mat[lin][col+1] != ' ') && (t->mat[lin-1][col] != ' ') &&  (t->mat[lin][col-1] != ' '))
  return 0;
}
// FIM LABLIB.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 *);
void empilha (struct pilha *, int , int);
void desempilha (struct pilha *);
//FIM PILHALIB.H

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

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

void libera_pilha (struct pilha *topo)
{
 struct pilha *p= malloc(sizeof(struct pilha));
 
 while (topo->prox != NULL)
      {
       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 = malloc (sizeof(topo));
 if (topo == NULL)
   return 1;
 return 0;
}

void empilha (struct pilha *topo, int lin, int col)
{
 if (pilha_cheia(topo))
   {
    printf("Pilha cheia!!\n");
    exit(1);
   }
/* else if (pilha_vazia(topo))
   {
    topo->pos.x=lin;
    topo->pos.y=col;
    topo->prox=NULL;
   } */
 else
   {
    struct pilha *p = (struct pilha *) malloc (sizeof(p));
    p->pos.x= lin;
    p->pos.y= col;
    p->prox= topo;
    topo=p;
   }  
}

void desempilha (struct pilha *topo)
{
 struct pilha *p= (struct pilha *) malloc (sizeof(p));
 
 if (pilha_vazia(topo))
   {
    printf("Pilha vazia!!\n");
    exit(1);
   }
 
 p=topo;
 topo=topo->prox;
 free(p);  
}

void desempilha_com_chave (struct pilha *topo, struct coordenada chave)
{
 struct pilha *p= (struct pilha *) malloc (sizeof(p));
 
 if (pilha_vazia(topo))
   {
    printf("Pilha vazia!!\n");
    exit(1);
   }
 while ((topo->pos.x != chave.x) && (topo->pos.y != chave.y))
      {
       p=topo;
       topo=topo->prox;
       free(p);  
      } 
}
//FIM PILHALIB.C