1 votos

Laberinto de Dijkstra y adyacencia -- Sopa de letras

He intentado resolver el siguiente problema utilizando la matriz de adyacencia para encontrar el camino más corto entre la entrada y la salida de este laberinto. El truco de esto es que no se puede salir de un nodo usando el mismo color con el que se ha entrado por lo que cada nodo acaba siendo 3, uno para cada color, y se obtiene una matriz de adyacencia asimétrica y con software resolver el grafo dirigido usando dijsktra. El problema que tengo es que me he pasado un montón de horas intentando resolverlo pero no consigo hacer bien la matriz de adyacencia y no encuentro información sobre este problema en internet. Cada vez que rehago la matriz de adyacencia el algoritmo no encuentra el camino más corto así que empiezo a preguntarme si no hay camino posible entre los dos puntos. Lo publico aquí por dos razones:

  1. Este problema se publicó en la revista Scientific American, así que quizá alguien de aquí haya visto antes este laberinto y conozca la respuesta.
  2. ¿Hay alguna forma más sencilla de hallar la matriz de adyacencia o de resolverla para evitar trabajar con una matriz de 61x61? (¿Quizás algún software donde pueda dibujar manualmente el grafo y luego resolverlo o algo similar?)

Por ahora lo resuelvo con matlab. Intentaré subir el archivo .m que contiene la matriz con la que he estado trabajando por si a alguien le puede interesar comprobarlo. Cualquier información será muy apreciada. Gracias

Alphabet Soup

0voto

richard Puntos 1

Una solución es HRTHAOWBENK. Lo encontré en pocos minutos a mano, yendo desde el final hasta la parte superior y tratando de llegar a la parte inferior.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X