Parte 2 - Segunda estratégia: função resolve usando PILHA

Esta segunda estratégia é muito parecida com a anterior com a única diferença que usaremos agora uma estrutura de dados do tipo PILHA ao invés de uma FILA.

Como vimos em sala de aula, uma lista ligada pode representar uma PILHA, criando-se um ponteiro para o início da lista, chamado topo, e fazendo a inserção e remoção de células somente no topo da PILHA.

Como na estratégia anterior, uma estrutura de dados do tipo PILHA nos permitirá guardar as posições dos diversos caminhos do labirinto. Esta estratégia de busca também é conhecida por Busca em Profundidade e apesar de ter a propriedade de ser mais eficiente em termos de utilização de memória, não garante encontrar uma solução de caminho mais curto como na estratégia anterior.

Essa estratégia começa inserindo na PILHA uma única célula com a posição inicial do rato e endereços nulos para os ponteiros próximo e pai. A busca pela posição do queijo é feita repetindo-se as seguintes instruções:

1. selecione o primeiro elemento da pilha, ou seja, o elemento apontado por topo_pilha
2. se topo_pilha == NULL então devolva NULL
3. se topo_pilha é a posição do queijo então devolva topo_pilha
4. senão remova o topo da pilha inserindo-o no início da lista LIXO (inicio_lixo)
5. insira na pilha todas as células sucessoras de inicio_lixo atribuindo ao campo pai o endereço de inicio_lixo

Devemos novamente marcar durante a busca as posições já visitadas com o caractere 'o' na matriz do labirinto, para evitar que sejam inseridas células já visitadas na PILHA. Não esqueça da inicialização e liberação da memória usada.

Assim que o algoritmo encontrar a posição do queijo você deve limpar as marcas do labirinto feitas durante a busca e, em seguida, marcar novamente as posições do caminho solução encontrado.