PRÁCTICA Nº 8: 1 sesión (del 22 a 26 de Mayo de 2000)

Resolución de un Laberinto Mediante un Árbol

Objetivos

  1. Implantación de árboles cuaternarios, generados a partir de una matriz.

  2. Recorrido del árbol para encontrar el camino entre la entrada y la salida.

Especificaciones

El trabajo a realizar se puede estructurar en tres tareas diferenciadas:

Tarea 1:

Leer un fichero en el que se encuentra guardada la información relativa al laberinto y guardar la información en una matriz bidimensional (Fichero de ejemplo labe.dat).

Tarea 2:

Convertir la matriz bidimensional en un árbol cuaternario, que contendrá como nodo raiz la casilla de entrada en el laberinto, y como nodos terminales tanto la casilla de salida del laberinto como los diferentes finales de caminos sin salida.

Tarea 3:

Recorrer el árbol buscando los diferentes caminos que empezando en la raíz tengan como final la casilla de salida del laberinto.

Realización de la Práctica

Tarea 1:

El laberinto estará guardado en un fichero de texto que contendrá como primer elemento el número de filas del laberinto y como segundo elemento el número de columnas del laberinto. A continuación contendrá una serie de números que serán la descripción del laberinto ateniendo a la siguiente codificación (un número por linea)(Fichero de ejemplo labe.dat):

0: Espacio libre

1: Pared

2: Entrada

3: Salida

La primera tarea que tendrá que realizar el programa es pedir un nombre de fichero al usuario y leer la información contenida en el fichero guardándola en una variable de tipo ‘laberinto’, descrita más adelante.

Tarea 2:

El proceso de generación del árbol se realizará siguiendo el siguiente algoritmo, partiendo de la casilla de entrada situada en la posicion ‘x=2, y=2.:

Situados en una cierta casilla ( x, y ):

a.- Si es un espacio libre, una entrada o una salida, y no esta visitada:

1. La marcamos como visitada.

2. Generamos un nodo del árbol y ponemos como información del nodo la posición de la casilla.

3. Para cada una de las cuatro direcciones de movimiento posible aplicamos el mismo algoritmo para uno de los hijos del nodo generado.

b. Sino el hijo es VACIO

Tarea 3:

Recorrer el árbol de forma prefija en busca de posibles caminos que comenzando en el nodo raiz (Entrada) termine en un nodo marcado como Salida.

 

Representación de la práctica

Para la representación del laberinto y el camino seguido por su interior, se utilizará una unidad ya compilada proporcionada por el profesor llamada ‘Dibu_Lab.Tpu’ que tiene la siguiente interfaz:

Interface

   Uses
         Crt;

   Const

      MAX_FIL = 80;
      MAX_COL = 24;

   Type
      Laberinto = Record
                     Info: Array[1..MAX_COL, 1..MAX_FIL] Of 0..3;
                     Visi: Array[1..MAX_COL, 1..MAX_FIL] Of Boolean;
                     Fil: 1..MAX_FIL;
                     Col: 1..MAX_COL;
                  End;

      Posicion = Record
                    x: 1..MAX_COL;
                    y: 1..MAX_FIL;
                 End;

   Procedure DibujaLaberinto ( labe: Laberinto );
   Procedure Marcar          ( posi: Posicion  );
   Procedure Desmarcar       ( posi: Posicion  );

Entrega de programas

Al finalizar la práctica correspondiente, se entregará al profesor un programa en Pascal llamado ‘laberi.pas’. Opcionalmente, se podrá dividir el programa en una unidad de trabajo con árboles (‘Uni_ArbQ.pas’) y un programa principal


ENTREGA DE PROGRAMAS: Al finalizar la sesión de prácticas correspondiente.