Programación General > C/C++
Búsqueda de caminos
(1/1)
player_:
Hola, tengo un fichero de texto con un laberinto de este estilo que lo cargo en una matriz:
##############E######## ####
# ## # #### # #
# ########
########### #####S#########
Una vez cargado, quiero comprobar si existe un camino válido, es decir, que puedo llegar desde E(entrada) hasta S (salida) sin problemas. En este caso debería indicarme que sí, pero por ejemplo, en este otro:
##############E######## ####
# ## # #### ### ## #
# ##########
########### #####S#########
Debería decirme que no porque hay una '#' bloqueando la entrada, tampoco podría si bloquea la salida o hay símbolos '#' que cortan el paso entre la entrada y la salida en cualquier punto de la matriz.
La entrada y salida pueden estar en cualquiera de los bordes del rectangulo, asi que cada vez habra que buscar un camino distinto según la situación.
Tenéis algún ejemplo o link para hacer esto con algún algoritmo de búsqueda en amplitud o algo parecido?
Lo necesitaría en C o C++.
Gracias.
Gared12:
Que tal player, mi recomendación sería que copiaras todo tu archivo a una matriz de [x][y] tu le pones los valores dependiendo de tu fichero puedes usar un contador de lecturas para calcular cuantas filas y columnas como máximo contiene, ya teniendo el fichero en memoria nada mas tendrias que identificar la Entrada y la Salida y ya mediante las coordenadas donde se encuentran revisar en la coordenas alrededor es decir si en (X,Y) se encuentra la entrada revisas en (X-1,Y) Y EN (X+1,Y) esto es para revisar que no se encuentre un "#" a la izquieda o la derecha y despues con una bandera marcas si se encuentra bloqueda por esos lados despues buscas en la (X+Y-1) Y EN (X+Y+1) y esto es para buscar a los lados si tu Entrada o Tu salida resultan con "#" en las 4 coordenadas alrededor entonces no se puede completar el camino.
Saludos espero que te ayude.
:hitcomp: Gared
player_:
Gracias, lo tendré en cuenta.
Navegación
Ir a la versión completa