Autor
|
Tema: urgente!ayuda, Laberinto C++ (Leído 5,639 veces)
|
RuKsu
Desconectado
Mensajes: 5
|
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.
|
|
|
En línea
|
|
|
|
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.
|
|
|
En línea
|
"When People called me freak, i close my eyes and laughed, because they are blinded to happiness" Hideto Matsumoto 1964-1998
|
|
|
RuKsu
Desconectado
Mensajes: 5
|
Gracias, pero honestamente sigo sin entender, igual voy a tratar de analizar tu respuesta, y ver si puede llegar a aplicarla
|
|
|
En línea
|
|
|
|
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.
|
|
|
En línea
|
"When People called me freak, i close my eyes and laughed, because they are blinded to happiness" Hideto Matsumoto 1964-1998
|
|
|
RuKsu
Desconectado
Mensajes: 5
|
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
|
|
|
En línea
|
|
|
|
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 Y ya tienes una matriz de 10x10, pero como mejor lo veas
|
|
|
En línea
|
"When People called me freak, i close my eyes and laughed, because they are blinded to happiness" Hideto Matsumoto 1964-1998
|
|
|
RuKsu
Desconectado
Mensajes: 5
|
Oka gracias voy a ver como puedo continuarlo
|
|
|
En línea
|
|
|
|
sebah97
Desconectado
Mensajes: 77
|
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.
|
|
|
En línea
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
[Ayuda] Necesito el Laberinto de MCKSys Argentina
Programación Visual Basic
|
sebah97
|
5
|
3,484
|
23 Junio 2010, 19:37 pm
por sebah97
|
|
|
Ayuda con laberinto en una matriz
Programación C/C++
|
edotropic
|
5
|
4,785
|
20 Diciembre 2013, 13:29 pm
por leosansan
|
|
|
Ayuda, Codigo Laberinto
Programación C/C++
|
RuKsu
|
0
|
2,785
|
10 Diciembre 2014, 21:03 pm
por RuKsu
|
|
|
Ayuda backtraking laberinto
Java
|
fenixskate
|
0
|
1,502
|
14 Octubre 2015, 19:57 pm
por fenixskate
|
|
|
ayuda urgente laberinto con grafos
Programación C/C++
|
blaaaack
|
0
|
3,968
|
20 Junio 2017, 02:33 am
por blaaaack
|
|