Parte 1 - Primeira estratégia: função resolve usando FILA

Usar uma estrutura de dados do tipo FILA nos permitirá guardar as posições dos diversos caminhos do labirinto (antes representados implicitamente pelas chamadas recursivas de resolve). Esta estratégia de busca também é conhecida por Busca em Largura e tem a propriedade de encontrar uma solução de caminho mais curto.

Como vimos em sala de aula, uma lista ligada pode representar uma FILA, criando-se ponteiros para o início (inicio_fila) e fim da lista ( fim_fila) sendo a inserção feita no fim e remoção no início da FILA.

Essa primeira estratégia começa inserindo na FILA vazia uma 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 FILA, ou seja, o elemento apontado por inicio_fila
2. se inicio_fila == NULL então devolva NULL
3. se inicio_fila é a posição do queijo então remova primeiro elemento da FILA inserindo-o na lista LIXO e devolva inicio_lixo
4. senão insira na FILA todas as posições vizinhas (células sucessoras), atribuindo ao campo pai dessas células, o endereço em inicio_fila;
5. remova primeiro elemento da FILA inserindo-o no início da lista LIXO

A matriz do labirinto, além de ser usada para determinar as novas posições a serem visitadas (células sucessoras), também será usada para evitar que sejam inseridas células já visitadas na FILA. Para isso, marcaremos as posições já visitadas com o caractere 'o', na matriz do labirinto. Não esqueça também 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 (com o caractere 'o'). Para isso, basta recuperar as células já visitadas que foram armazenadas na lista lixo, percorrendo-a através do ponteiro pai a partir do endereço da célula devolvido pela função resolve_fila.