O Labirinto

Algoritmos e Estruturas de Dados I
Prof. Daniel M. Martin
([e-mail])
Aula 9 (laboratório)

O Labirinto

Descrição do problema
●

●

●

O problema é achar o caminho entre dois pontos de interesse num labirinto
Os dois pontos de interesse são o “rato” e o
“queijo”
Você deve ajudar o rato a achar o queijo

Exemplo

Descrição do problema
●

●

●

●

O labirinto é um dado do problema e pode ser visto como uma matriz m x n m = número de linhas; n = número de colunas
(no exemplo anterior m = n = 6)
Você pode sempre supor que o labirinto é fechado, isto é, que há paredes ao redor do labirinto para impedir o rato de sair
O labirinto será dado na entrada padrão codificado como um arquivo texto

Descrição do problema
●

Codificação genérica de um labirinto: m n a11 a12 a13 . . . a1m a21 a22 a23 . . . a2m
.
.
.
an1 an2 an3 . . . anm

●

Cada a ij vale:
–

0 – posição livre

–

1 – posição rato

–

2 – posição queijo

–

3 – parede

Codificação do labirinto do exemplo
●

Salvar o texto abaixo num arquivo teste.txt
6
3
3
3
3
3
3

6
3
1
0
0
0
3

3
3
3
0
3
3

3
2
3
0
0
3

3
0
0
0
3
3

3
3
3
3
3
3

Lendo o labirinto da entrada
●

●

O arquivo main.c (antigo labirinto.c) contém uma função que lê um labirinto da entrada
Os dados lidos são armazenados numa estrutura labirinto que é definida por: struct s_labirinto { int linhas; int colunas; int **M;
}
typedef struct s_labirinto labirinto;

Já implementado (em main.c)
/* le os dados da entrada e devolve variável do tipo labirinto */ labirinto le_labirinto_da_entrada();
/* aloca espaço para uma matriz de inteiros com m linhas e n colunas */
// usada em le_labirinto_da_entrada() int **aloca_matriz(int m, int n);
/* libera uma matriz M com m linhas que havia sido alocada dinamicamente */ void libera_matriz(int **M, int m);

Já implementado (em main.c)
/* imprime o labirinto na saída padrão */ void imprime_labirinto(labirinto L);
/* uma função main de exemplo de uso das funções de labirinto */ int main() {