Backtracking - Laberinto

[hadree]

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

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 [Seleccionar] Expandir



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 [Seleccionar] Expandir



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 [Seleccionar] Expandir


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



.

[Garfield07]

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

[pucheto]

Me parece q es un mal ejemplo para backtracking. Sale por djkstra...

[do-while]

¡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!