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

 

 


Tema destacado: Recopilación Tutoriales y Manuales Hacking, Seguridad, Privacidad, Hardware, etc


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

Desconectado Desconectado

Mensajes: 6


Ver Perfil
Backtracking - Laberinto
« en: 22 Noviembre 2010, 17:12 pm »

************************************

Hola a todos, soy nuevo en el foro y se ma ha ocurrido la idea de este hilo para explicar como realizar el algoritmo de "backtracking" para calcular el camino de ida desde la entrada de un laberinto, hasta la salida del mismo (en caso de haberla).

Os propongo realizar un pequeño programa que cumpla lo siguiente:

Código:

Dado un laberinto escriba un programa que usando
los cuatro movimientos del laberinto, arriba, abajo,
izquierda y derecha calcule (si existen):

1) La primera solución.
2) El total de las soluciones
3) La mejor solución en cuanto a menor número de pasos.

Los datos de entrada son recibidos en un fichero
de texto laberinto.txt que tiene la siguiente estructura:

a.) La primera línea tiene dos números enteros que
son el número de filas nf y el número de columnas nc  del laberinto.
b.) Las siguientes nf líneas tienen un total de nc números enteros cada
una de ellas separados por blancos que pueden ser: 0, 1, 2, 3 y 4

CERO: Indica muro (no se puede pisar la casilla);
UNO: Libre sin penalización. (+1 pasos)
DOS: Libre con penalización. (+2 pasos)
TRES: Libre con penalización. (+3 pasos)
CUATRO: Libre con penalización. (+4 pasos)

c.) La última línea del fichero tiene cuatro números enteros:

Fe = fila de entrada.
Ce = columna de entrada.
Fs = fila de salida.
Cs = columna de salida.


Código:

La estructura del laberinto en el archivo sería la siguiente:

---------------------------
nf nc
x x x x x x x x
x x x x x x x x
x x x x x x x x
x x x x x x x x
x x x x x x x x
fe fs ce cs
---------------------------
12 12
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 0 0 1 1 1 0
0 4 0 4 0 4 3 3 4 0 4 0
0 3 0 2 0 3 0 1 0 0 1 0
0 4 0 3 0 3 0 1 0 1 4 0
0 3 0 4 0 3 0 4 0 1 0 0
0 4 0 1 1 1 3 1 2 1 0 0
0 3 0 0 1 0 0 1 0 1 3 1
0 4 0 0 1 1 0 2 0 4 0 0
0 2 0 0 0 1 0 3 0 4 0 0
0 1 1 1 1 1 0 4 1 4 3 0
0 0 0 0 0 0 0 0 0 0 0 0
1 0 7 11
---------------------------


Os animáis a intentarlo :cool: ??

Código:
//El código lo pondré en unos días, a ver si la gente participa...:D


.


« Última modificación: 22 Noviembre 2010, 17:14 pm por hadree » En línea

Garfield07


Desconectado Desconectado

Mensajes: 1.121


¡Este año voy a por todas! JMJ 2011


Ver Perfil WWW
Re: Backtracking - Laberinto
« Respuesta #1 en: 22 Noviembre 2010, 19:00 pm »

Seria un code interesante para estudiarlo xD!!!
A ver como te queda!!!


En línea



* Quiero cambiar el mundo, pero estoy seguro de que no me darían el código fuente.
* No estoy tratando de destruir a Microsoft. Ese será tan solo un efecto colateral no intencionado.
* Si compila esta bien, si arranca es perfecto.

¡Wiki elhacker.net!
Un saludo
pucheto

Desconectado Desconectado

Mensajes: 215


Ver Perfil
Re: Backtracking - Laberinto
« Respuesta #2 en: 23 Noviembre 2010, 02:49 am »

Me parece q es un mal ejemplo para backtracking. Sale por djkstra...
En línea

do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Backtracking - Laberinto
« Respuesta #3 en: 23 Noviembre 2010, 03:08 am »

¡Buenas!

¿Dijkstra?

No conocia el metodo. Todos los dias se aprende algo. Ahora lo miro. Cuando aprendi lo que era el backtracking, el primer ejemplo de aplicacion que me pusieron fue un laberinto...

¡Saludos!
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[Reto] Backtracking - Laberinto
.NET (C#, VB.NET, ASP)
hadree 7 13,944 Último mensaje 17 Diciembre 2010, 13:35 pm
por pisa2
Suma de Conjuntos con Vuelta Atrás (Backtracking) en C
Programación General
maritere22 6 8,406 Último mensaje 31 Mayo 2013, 05:39 am
por Kenkox
BACKTRACKING CIRCUITO HAMILTONIANO
Programación C/C++
yeah_2796 1 2,915 Último mensaje 23 Mayo 2015, 11:19 am
por Stakewinner00
problema de backtracking y programacion dinamica
Programación C/C++
aprendiz de programador 6 6,531 Último mensaje 12 Diciembre 2015, 16:08 pm
por SnzCeb
regex para email catastrophic backtracking
PHP
gAb1 4 3,093 Último mensaje 20 Abril 2016, 17:32 pm
por gAb1
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines