rato locão no labirinto

q4.c

//Equipe: Pablo AS Hugen
//Questão 04: Fuga do labirinto
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_LEN 10000

/*Estruturas da pilha e de coordenadas*/
typedef struct
{
	int i,j;
}coord;

typedef struct Lnode
{
	struct Lnode *Next;
	coord Data;
	struct Lnode *Prev;
}Lnode;

typedef struct Lhead
{
	Lnode *First;
	int Lenght;
	Lnode *Last;
}Lhead;

/*Estrutura do labirinto, armazena a matriz dos caracteres,
 * e as coordenadas de entrada e saída */
typedef struct
{
	/*Dimensões do labirinto*/
	int m,n;
	/*Matriz que representa o labirinto*/
	char **matriz;
	/*Coordenadas de entrada e saída*/
	coord in,out;

}Labirinto;


/*Funções sobre o labirinto*/
int saidaLab(Labirinto *l, Lhead *p, Lhead *t);
void scanLab(Labirinto *l, int m, int n);
void freeLab(Labirinto *l);
void printLab(Labirinto *l);
void caminhoLab(Labirinto *l, Lhead *p);

/*Funçoes sobre a listaDE/pilha*/
void initStack(Lhead *l);
void freeStack(Lhead *l);
void printStack(Lhead *l);
int push(Lhead *l, coord Data);
coord pop(Lhead *l);
coord onTop(Lhead *l);
int isEmptyStack(Lhead *l);

int main()
{
	Lhead p,t;
	Labirinto l;
	int m, n;
	
	initStack(&p);	
	initStack(&t);
	
	scanf("%d %d", &m, &n);
	scanLab(&l, m, n);
	if(saidaLab(&l, &p, &t))
	{
		printf("S\n");
		printStack(&p);
		printStack(&t);
		printf("%d\n",p.Lenght);
		printf("%d\n",t.Lenght);
		caminhoLab(&l, &p);
		printLab(&l);
	}
	else
		printf("N\nLabirinto sem saída.\n");

	freeStack(&p);
	freeStack(&t);
	//freeLab(&l);
}

int saidaLab(Labirinto *l, Lhead *p, Lhead *t)
{
	coord posAtual = l->in;
	/*coordenadas para a pilha*/
	coord posProx;
	int flagSemSaida;

	while(!(posAtual.i == l->out.i && posAtual.j == l->out.j))
	{

		l->matriz[posAtual.i][posAtual.j] = '.';
		flagSemSaida =1;
		//push(t, posAtual);

		printLab(l);
		/*Empilha o vizinho da esquerda*/
		if(posAtual.j-1>=0 && (l->matriz[posAtual.i][posAtual.j-1] == '0' ||
				       l->matriz[posAtual.i][posAtual.j-1] == 's'))
		{
			posProx.i = posAtual.i;
			posProx.j = posAtual.j-1;
			push(p, posProx);
			flagSemSaida =0;
		}
		/*Empilha o vizinho de baixo*/
		if(posAtual.i+1<l->m && (l->matriz[posAtual.i+1][posAtual.j] == '0' || 
					 l->matriz[posAtual.i+1][posAtual.j] == 's'))
		{
			posProx.i = posAtual.i+1;
			posProx.j = posAtual.j;
			push(p, posProx);
			flagSemSaida =0;
		}
		/*Empilha o vizinho da direita*/
		if(posAtual.j+1<l->n && (l->matriz[posAtual.i][posAtual.j+1] == '0' ||
				         l->matriz[posAtual.i][posAtual.j+1] == 's'))
		{
			posProx.i = posAtual.i;
			posProx.j = posAtual.j+1;
			push(p, posProx);
			flagSemSaida =0;
		}
		/*Empilha o vizinho de cima*/
		if(posAtual.i-1>=0 && (l->matriz[posAtual.i-1][posAtual.j] == '0' ||
				       l->matriz[posAtual.i-1][posAtual.j] == 's'))
		{
			posProx.i = posAtual.i-1;
			posProx.j = posAtual.j;
			push(p, posProx);
			flagSemSaida =0;
		}
		
		/*Todas as possibilidades foram esgotadas e o rato não saiu*/
		if(isEmptyStack(p)) 
			return 0;

		if(flagSemSaida)
		{
			pop(p);
			pop(t);
			if(!isEmptyStack(p)) posAtual = onTop(p);
		}
		else
		{
			push(t,posAtual);
			posAtual = onTop(p);
		}

	}
	/*O rato chegou ao final*/
	push(t, l->out);
	return 1;

}

void scanLab(Labirinto *l, int m, int n)
{
	int i;
	/*possivel ocorrência da entrada ou saída em alguma linha*/
	char *ocu_in, *ocu_out;

	char *tmp = (char *)malloc((n+1) * sizeof(char));
	l->m = m;
	l->n = n;

	/*Aloca o array de ponteiros para arrays de caractres*/
	l->matriz = (char **)malloc(m*sizeof(char*));

	/*Aloca e lê as linhas individuais*/
	for(i=0; i<m; i++)
	{
		*(l->matriz+i) = (char *)malloc((n+1)*sizeof(char));
		scanf("%s", tmp);
		//printf("%s\n",tmp);
		
		ocu_in = strchr(tmp, 'e');
		ocu_out = strchr(tmp, 's');

		/*Encontrou entrada ou saída*/
		if(ocu_in)
		{
			l->in.i = i;
			l->in.j = ocu_in - tmp;
			ocu_in = NULL;
		}
		else if(ocu_out)
		{
			l->out.i = i;
			l->out.j = ocu_out - tmp;
			ocu_out = NULL;
		}
		strcpy(l->matriz[i], tmp);
	}	
	free(tmp);
}

void freeLab(Labirinto *l)
{
	int i;
	for(i=0; l->m; i++)
		free(l->matriz[i]);
}

void printLab(Labirinto *l)
{
	int i;

	for(i=0; i<l->m; i++)
		printf("%s\n", *(l->matriz+i));

	//printf("\n");
	//printf("\nEntrada: (%d, %d)\nSaída: (%d, %d)\n", l->in.i, l->in.j, l->out.i, l->out.j);
}

void caminhoLab(Labirinto *l, Lhead *p)
{
	int i,j;
	Lnode *aux = p->First;
	/*'Pinta' as posições com '.'*/
	l->matriz[l->in.i][l->in.j] = 'e';
	for(i=0; i<l->m; i++)
		for(j=0; j<l->n; j++)
			if(l->matriz[i][j] == '.')
				l->matriz[i][j] = '0';
	/*Traça o caminho do que o rato percorreu*/
	while(aux)
	{
		l->matriz[aux->Data.i][aux->Data.j] = '*';
		aux = aux->Next;
	}
	l->matriz[l->out.i][l->out.j] = 's';

}

void initStack(Lhead *l)
{
	l->First = l->Last = NULL;
	l->Lenght = 0;
}

void freeStack(Lhead *l)
{
	Lnode *aux = l->First;

	while(aux)
	{
		/* Desacopla o primeiro nó */
		l->First = l->First->Next;
		if(l->First)
			l->First->Prev = NULL;

		/* Desaloca o primeiro nó e vai para o próximo */
		free(aux);
		aux = l->First;
	}
	initStack(l);
}
void printStack(Lhead *l)
{
	Lnode *aux;

	aux = l->Last;
	while(aux)
	{
		/*Printa o valor das coordenadas para se adequar ao index
		 * começando em 1*/
		printf("%s(%d,%d)%s",(aux==l->Last)?("["):(""),
				aux->Data.i+1,
				aux->Data.j+1,
				(aux->Prev==NULL)?("]\n"):(", "));
		aux = aux->Prev;
	}
}

int push(Lhead *l, coord Data)
{
	Lnode *no = (Lnode *)malloc(sizeof(Lnode));

	/* Se a alocação Falhou */
	if(no == NULL)
		return 1;

	/* Faz o nó apontar para os vizinhos */
	no->Prev = NULL;
	no->Data = Data;
	no->Next = l->First;

	/* Faz os vizinhos apontarem para o nó,
	 * trata o caso da lista vazia */
	if(l->Last == NULL)
		l->Last = no;
	else
		l->First->Prev = no;

	l->First = no;
	l->Lenght++;

	return 0;
}

coord pop(Lhead *l)
{
	Lnode *aux = l->First;
	coord ret = l->First->Data;

	/* A lista tem só um elemento */
	if(l->First == l->Last)
		l->First=l->Last = NULL;
	else
	{
		l->First->Next->Prev = NULL;
		l->First = l->First->Next;
	}

	l->Lenght--;
	free(aux);

	return ret;

}
coord onTop(Lhead *l)
{
	return l->First->Data;
}

int isEmptyStack(Lhead *l)
{
	return(l->First == NULL);
}