A Documentação Código Labirinto

INTRODUÇÃO

Nesse trabalho tivemos que desenvolver um algoritmo que leia um arquivo de texto com um labirinto e os seus dados e achar o caminho mais curto até a saída e imprimir essa saída na tela e salvá-la num arquivo de texto. Eu particularmente gostei de fazer esse trabalho, pois consegui reforçar alguns conhecimentos usando as estruturas de dados pilhas e listas, e também na parte de alocação dinâmica.

IMPLEMENTAÇÃO

A seguir mostrarei as implementações das classes “Pilha.h”, “Lista.h” e “Labirinto.h”.

[pic 1][pic 2]

Em “Pilha.h” e “Pilha.c”, foram implementadas funções básicas para o controle da pilha (excluir, inserir, inicializar). Já em “Lista.h” e “Lista.c” foram implementadas as funções básicas e também uma função para buscar um elemento na lista.

[pic 3]

A caixa de texto acima é o arquivo “Labirinto.h”, cujas funções são usadas no arquivo

“Labirinto.c” e “main.c”.

[pic 4]A seguir mostrarei a parte principal (onde o labirinto é solucionado) em pseudocode.

funcao solucionaLabirinto(lab: labirinto): inteiro var

caminhoAtual: lista historico: pilha

e :TNodo

ep: TElemento passos: inteiro

inicio

//cria a pilha e verifica se ela foi criada historico <- criaPilha()

se !historico entao

retorne 0

//cria a lista e verifica se ela foi criada caminhoAtual <- criaLista()

se !caminhoAtual entao

retorne 0

//define as cordenadas de inicio e adiciona na lista e.coluna <- labirinto->ye

e.linha <- labirinto->xe ep.chave <- e

insereFim(caminhoAtual, e.linha,e.coluna) ep.controle <- 0

repita

//conta a quantidade de passos dadas para a solucao do labirinto

se (lab->m[e.linha, e.coluna] == “0”) ou (lab->m[e.linha, e.coluna] == “*”) entao passos<-passos+1

lab->m[e.linha, e.coluna] <- “&”

fimse

//exibe o labirinto em tempo real de execucao exibeLabirinto(lab)

sleep(100)

//substitui o caminho percorrido por '*'(asteristicos)

se(e.linha == lab->xe e e.coluna == lab->ye) entao lab->m[e.linha, e.coluna] <- “*”

senao

lab->m[e.linha, e.coluna] <- “*”

fimse

//se chegar no final do labirinto o laço ira parar if((e.coluna == lab->ys && e.linha == lab->xs)) interrompa

limpatela

//verifica se pode andar para a esquerda e se o caminho está livre

se(ep.controle < 1 e caminhoLivre(lab, caminhoAtual, e.linha, e.coluna - 1)) entao

//armazena a direcao (1-esquerda,2-Direita,3-Cima,4-Baixo) ep.controle <- 1

//insere a posicao na pilha push(historico, ep)

//decrescenta a coluna para a esquerda e guarda na lista e.coluna<- e.coluna-1

ep.chave.coluna<- ep.chave.coluna-1; insereFim(caminhoAtual, e.linha, e.coluna);

//reseta a direcao para continuar a percorrer o labirinto ep.controle <- 0

senao

//verifica se pode andar para a direita e se o caminho está livre

se(ep.controle < 2 e caminhoLivre(lab, caminhoAtual, e.linha, e.coluna + 1)) entao

//armazena a direcao (1-esquerda,2-Direita,3-Cima,4-Baixo) ep.controle <- 2

//insere a posicao na pilha push(historico, ep);

//acrescenta a coluna para a direita e guarda na lista e.coluna<- e.coluna+1

ep.chave.coluna<- ep.chave.coluna+1 insereFim(caminhoAtual, e.linha, e.coluna)

//reseta a direcao para continuar a percorrer o labirinto ep.controle <- 0

senao

//verifica se pode andar para cima e se o caminho está livre

se(ep.controle < 3 e caminhoLivre(lab, caminhoAtual, e.linha - 1, e.coluna)) entao

//armazena a direcao (1-esquerda,2-Direita,3-Cima,4-Baixo) ep.controle <- 3