urgente!ayuda, Laberinto C++

[RuKsu]

Hola soy nuevo en el foro, y necesito ayuda en un trabajo que tengo que hacer para el colegio, básicamente no entiendo como hacer cada cosa pero si crear la matriz, etc. El ejercicio es el siguiente :
Se dispone de una matriz de N x M que representa un laberinto compuesto de paredes y baldosas (1 y 0), este laberinto consta de entradas ubicadas en la primera fila y salidas en la última fila.
Se pide:
-Encontrar todos los caminos hacia la salida.
-Almacenar en una lista simplemente encadenada los pasos que se involucran en camino.
-N y M son valores ingresados por el usuario.
-Mostrar matriz y la lista.
Gracias por su ayuda.

[Orubatosu]

Existen varios métodos para encontrar la salida de un laberinto, y el mas conocido o mas usado es la regla de "la mano derecha", que consiste en tomar una posición inicial, compruebas si se puede ir a la derecha, si no, abajo, compruebas derecha, etc... siguiendo continuamente la derecha al final encuentras la salida (siempre que no este dentro del laberinto, y este no es el caso).

Eso si, tienes un desafío interesante para el algoritmo, no debería de ser "muy dificil" pero si un poco laborioso, ya que deberás de comprobar cuando se vuelve sobre tus pasos marcar esas casillas como "duplicadas" para encontrar el camino mas corto.

Supongo que se podría crear tuplas de las casillas, y con ellas vectores que te vayan almacenando el camino, siendo el final de cada uno e inicio del siguiente la ultima casilla visitada dos veces (esto al vuelo, sin pensarlo mucho)

Y eso asumiendo una solución, encontrarlas todas puede ser mas "puñetero", pero supongo que a partir de esta idea general se puede empezar a trabajar.

[RuKsu]

Gracias, pero honestamente sigo sin entender, igual voy a tratar de analizar tu respuesta, y ver si puede llegar a aplicarla

[Orubatosu]

A ver si puedo expresarlo mejor...

Imaginemos una matriz tal que:

00000000010000000
00000000011110000
00000000000010000
00000000000110000
00000000000100000
00000001111111000
00001111000001000
00001000000001100
00000000000000100

Conviene empezar a afrontar este tipo de problemas con ejemplos lo mas simples posibles. Generalmente la solución para un ejemplo sencillo puede aplicarse a uno mas grande. El mismo algoritmo que nos vale para ordenar 3 números nos puede valer para ordenar un millón, solo que a la hora de plantearnos el problema es mucho mas sencillo plantearselos de la forma mas simple posible.

Empecemos con UNA sola posible solución, y a partir de ahi se puede empezar a desarrollar la idea.

¿Por donde empezamos nuestro recorrido?... pues recorremos la primera fila buscando un hueco en la pared, es decir: un uno.

Ya tenemos el inicio, que guardamos. A continuación ¿a donde nos movemos?... pues obviamente miramos los 4 lados, y si solo existe una posibilidad, la seguimos. Si existen dos, empezamos otra ruta "en reserva" y continuamos una de las existentes. De hecho podemos estar seguros de que en un punto dado, nunca tendremos mas de 3 posibilidades, a menos que las 3 que hemos seguido no salgan del laberinto (en cuyo caso toca retroceder a una bifurcación anterior)

Pero vamos, tenemos un punto de inicio, ¿hay solo un camino?... lo seguimos almacenandolo, y marcamos esos pasos. ¿Llegamos a un lugar donde hay 2 posibilidades?, escojemos uno y guardamos el otro para después, así hasta llegar a la última fila, donde obviamente hemos llegado a la salida.

¿Como almacenamos el mapa?... pues parece claro que sería una matriz, de tipo booleano de dos dimensiones, o "0" (pared) o "1" (pasillo), no hay mas misterio.

Para almacenar los diferentes recorridos, dado que no sabemos el numero de pasos necesarios podemos usar un vector o una lista. Ojo, hablo de vectores y listas como clases de C++ en la STD, si no los conoces podemos recurrir a un array clásico que sea lo bastante grande como para contener los movimientos (lo dimensiones a lo grande y a correr, de hecho la longitud mas larga posible sería la total de una fila multiplicado por la mitad de las columnas mas una columna (en realidad un poco menos, pero estoy improvisando sobre la marcha).

Es posible además que existan algoritmos mas eficientes, sería cuestión quizás de buscar un poco.

[RuKsu]

Gracias, tendría q hacer una clase matriz, crear la matriz, crear una clase laberinto el cual crea la matriz y realiza un backtracking. Voy a ver si lo puedo realizar, y en unos dias subo el código

[Orubatosu]

Tu verás, pero no veo necesario declarar una clase "matriz"... un simple arreglo de booleanos, o de cualquier otra cosa te vale

Por ejemplo un

Código [Seleccionar] Expandir


bool laberinto[10][10];


Y ya tienes una matriz de 10x10, pero como mejor lo veas

[RuKsu]

Oka gracias voy a ver como puedo continuarlo

[sebah97]

Perdón que desvirtúe... pero que edad tenés y a que colegio vas? Si en todos los colegios pedirían cosas como ésta te puedo asegurar que estaría lleno de genios.