Tarea Computacional

Recursividad. Programación. Laberinto

  • Enviado por: Sebastián Allendes
  • Idioma: castellano
  • País: Chile Chile
  • 6 páginas
publicidad

TAREA COMPUTACIONAL I

PROGRAMACIÓN II

El programa está basado en la recursividad de la función “mueve”, comienza parado en la posición (2,1), donde (x,y) = (posición horizontal, posición vertical).

Diremos que un casillero fue visitado si su valor es 2, que existe una muralla si su valor es 1, y que no ha sido visitado si su valor es 0.

Al entrar en la función, ella pregunta si se puede mover a la derecha, abajo, arriba, o a la izquierda, en ese orden. Si puede a la derecha, se llama recursivamente “mueve(3,1)”, volviendo a preguntar lo mismo, hasta que no puede moverse a ninguna parte.

Devolviéndose en la recursividad.

En cada movimiento, consideraremos sólo un casillero de la pieza, el derecho. Y las posibilidades de movimiento que ofrece esa pieza (2x1) serán restringidas en las funciones de confirmación de movimiento nombradas a continuación.

Esta función se ayuda de las funciones de confirmación del movimiento derecha, abajo, izquierda y arriba, las cuales devuelven 1 si se puede mover, y 0 si no. Además, la forma de la pieza (2x1) determina cómo están estructurada cada una de ellas.

Respondiendo que no se puede mover del casillero, si el casillero destino ya fue visitado (2), o que existe alguna muralla del laberinto (1).

Por otro lado, si no pasa lo anterior, el valor del casillero es (0), y si se puede mover, por lo tanto la función devuelve un 1.

En cada llamada de la función mueve, la función marca como leído el casillero llamado, e incrementa en 1 uno un contador `nj' que corresponde a número de movimientos. Y almacena la posición (x,y) de la movida en un arreglo, en el índice acumulado `nj'.

Si en la posición no se puede mover, es decir, llega al final de la función mueve, el contador `nj' disminuye en 1, ya que la pieza se tiene que devolver.

Además, en cada llamada de la función mueve, se pregunta si se está pasando en la salida, y si lo es, se asigna fin=1 y tj=nj (total de jugadas hasta llegar a la salida), lo que hace devolver inmediatamente la recursividad, procediendo a la parte de impresión en pantalla.

Si la pieza ya no puede ir a ninguna parte, es decir, se acaba la primera llamada de la función mueve(2,1) y no ha estado en la salida, fin=0.

Finalmente si fin=0, no tiene salida el laberinto.

Si fin=1, si tiene salida, y se procede a desplegar en pantalla las movidas.

Se puede modificar la salida y agregar o cambiar fácilmente murallas en el código fuente del programa.

Especificaciones:

El presente programa en C, sirve para encontrar la salida a un laberinto. Se dispone de un espacio cuadriculado de 100x100. Cada cuadricula puede estar libre u ocupada, configurando un “laberinto”. Se dispone de una “pieza” de cierta forma, en este caso (00), constituida por dos cuadrículas conectadas. Las direcciones de conexión, así como las de movimiento, son la izquierda, la derecha, arriba y abajo. Fijada una posición inicial se trata sacar la pieza del laberinto por una salida previamente fijada. Si no hay solución al problema, se debe advertir de ello al usuario. Si hay varias posibilidades, se debe buscar el camino más corto hacia la salida.