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:
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.