EP3 - Resolvendo o Labirinto com FILAS e PILHAS

Neste exercício programa você deverá implementar três estratégias diferentes da função resolve construida para o Problema do Labirinto do EP1
(http://www.ime.usp.br/~jose/mac122/ep1/).

A estratégia de solução empregada no EP1 foi a de backtracking usando recursão. A função resolve implementada desta maneira usou apenas uma matriz de caracteres para representar o labirinto.

Neste novo EP, além da matriz de caracteres, vamos usar estruturas de dados do tipo FILA e PILHA, implementadas como listas ligadas. Estas listas serão usadas para guardar caminhos no labirinto e procurar o caminho solução. As células das listas representarão posições (x,y) do labirinto e terão dois ponteiros:

1. um ponteiro proximo que contém o endereço do próximo elemento da lista e
2. um ponteiro pai que contém o endereço da célula que indica uma posição visitada anteriormente.

A definição de uma estrutura para a célula descrita desta maneira é dada por:

struct posicao
{
  int x, y;
  struct posicao *proximo, *pai;  
};

Através do ponteiro pai será possível representar vários caminhos no labirinto, incluindo o da solução desejada. Além das estruturas de FILA ou PILHA, usaremos uma lista de células removidas que chamaremos de LIXO.

Observe que todas as funções implementadas anteriormente poderão ser usadas neste EP, a saber:

char **alocamatriz(int m, int n);
void impressao(char **lab, int m, int n);
void libera_matriz(char **lab, int m);
char **leitura(int *m, int *n);

Para facilitar os testes e correção de seu ep, a função impressão deve ser modificada para imprimir o labirinto na tela, e não em arquivo como foi feito no EP1.