elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Sigue las noticias más importantes de seguridad informática en el ttwitter! de elhacker.NET


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  urgente!ayuda, Laberinto C++
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: urgente!ayuda, Laberinto C++  (Leído 3,899 veces)
RuKsu

Desconectado Desconectado

Mensajes: 5


Ver Perfil
urgente!ayuda, Laberinto C++
« en: 5 Diciembre 2014, 21:50 pm »

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


Desconectado Desconectado

Mensajes: 2.515


Ver Perfil WWW
Re: urgente!ayuda, Laberinto C++
« Respuesta #1 en: 5 Diciembre 2014, 22:01 pm »

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 Desconectado

Mensajes: 5


Ver Perfil
Re: urgente!ayuda, Laberinto C++
« Respuesta #2 en: 5 Diciembre 2014, 22:15 pm »

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


Desconectado Desconectado

Mensajes: 2.515


Ver Perfil WWW
Re: urgente!ayuda, Laberinto C++
« Respuesta #3 en: 5 Diciembre 2014, 22:43 pm »

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 Desconectado

Mensajes: 5


Ver Perfil
Re: urgente!ayuda, Laberinto C++
« Respuesta #4 en: 5 Diciembre 2014, 22:57 pm »

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


Desconectado Desconectado

Mensajes: 2.515


Ver Perfil WWW
Re: urgente!ayuda, Laberinto C++
« Respuesta #5 en: 6 Diciembre 2014, 14:54 pm »

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:
bool laberinto[10][10];

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 Desconectado

Mensajes: 5


Ver Perfil
Re: urgente!ayuda, Laberinto C++
« Respuesta #6 en: 7 Diciembre 2014, 05:17 am »

Oka gracias voy a ver como puedo continuarlo
En línea

sebah97

Desconectado Desconectado

Mensajes: 77



Ver Perfil
Re: urgente!ayuda, Laberinto C++
« Respuesta #7 en: 7 Diciembre 2014, 05:41 am »

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

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[Ayuda] Necesito el Laberinto de MCKSys Argentina
Programación Visual Basic
sebah97 5 2,307 Último mensaje 23 Junio 2010, 19:37 pm
por sebah97
Ayuda con laberinto en una matriz
Programación C/C++
edotropic 5 2,665 Último mensaje 20 Diciembre 2013, 13:29 pm
por leosansan
Ayuda, Codigo Laberinto
Programación C/C++
RuKsu 0 1,732 Último mensaje 10 Diciembre 2014, 21:03 pm
por RuKsu
Ayuda backtraking laberinto
Java
fenixskate 0 849 Último mensaje 14 Octubre 2015, 19:57 pm
por fenixskate
ayuda urgente laberinto con grafos
Programación C/C++
blaaaack 0 2,134 Último mensaje 20 Junio 2017, 02:33 am
por blaaaack
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines