O Labirinto

Páginas: 6 (1459 palavras) Publicado: 21 de abril de 2015
Algoritmos e Estruturas de Dados I
Prof. Daniel M. Martin
(daniel.martin@ufabc.edu.br)
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 doproblema 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 mlinhas 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() {labirinto L = le_labirinto_da_entrada();
imprime_labirinto(L);
libera_matriz(L.M, L.linhas);
return 0;
}

Compilando e rodando o exemplo
No linux
linux$
linux$
3 3 3
3 1 3
3 0 3
3 0 0
3 0 3
3 3 3
linux$

gcc
lab
3 3
2 0
3 0
0 0
0 3
3 3

main.c pilha.c item.c -o lab
< teste.txt
3
3
3
3
3
3

Compilando e rodando o exemplo
No windows








Crie um projeto no Dev C++ (ou Code::blocks)
Inclua osarquivos main.c, item.c e pilha.c
(e também item.h e pilha.h)
Compile seu programa (suponha que o
executável receba o nome de lab.exe)
Coloque o arquivo teste.txt no mesmo
diretório do programa executável lab.exe

Compilando e rodando o exemplo
No windows






Clique no menu iniciar e digite o comando cmd
e aperte a tecla ENTER
Um prompt de comando se abre
Navegue (usando o comando cd) até odiretório do seu executável (o mesmo do teste.txt)

Compilando e rodando o exemplo
No windows
C:\SeuProjeto> lab.exe < teste.txt
3 3 3 3 3 3
3 1 3 2 0 3
3 0 3 3 0 3
3 0 0 0 0 3
3 0 3 0 3 3
3 3 3 3 3 3
C:\SeuProjeto>

O que você deve fazer?








Achar o caminho do rato ao queijo usando a
estrutura de dados “pilha” e o algoritmo que
será explicado mais adiante
Para isso você deve usar osarquivos
pilha.h, pilha.c, item.h e item.c que
estão em labirinto.tar.gz
Você não pode modificar esses arquivos! (O
pessoal das 8:00 pode, mas é preferível que,
em vez disso, usem a nova versão no site.)
Estude o arquivo main.c (antigo labirinto.c)
Você deverá começar o trabalho a partir dele

Usando a estrutura labirinto
labirinto L = le_labirinto_da_entrada();
// para acessar as dimensões
// dolabirinto L você pode fazer
int m = L.linhas, n = L.colunas;
/* para acessar o código (0, 1, 2 ou 3)
da linha i e coluna j do labirinto, usar
a matriz L.M */
codigo = L.M[i][j];


Veja, por exemplo, o código da função
imprime_labirinto() em labirinto.c

Como explorar o labirinto?


Você precisará uma variável P do tipo pilha



A pilha armazena objetos do tipo item



O tipo item, para nós, será...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • labirinto
  • Labirinto
  • Labirinto
  • labirinto
  • Labirinto
  • labirinto
  • Labirinto
  • O labirinto

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!