El tesoro del templo (II)

Enunciado

Este problema, como es evidente, es muy parecido a "El tesoro del templo (I)", ya solucionado antes en el blog. La solución de este problema es similar, pero tiene una pequeña dificultad añadida.

En todos los problemas en los que se trata de recorrer un laberinto sin pasar dos veces por el mismo sitio, hay un principio que resulta a la vez muy útil y muy sencillo de entender. Todos los cruces que recorramos deben tener un número par de caminos que lleguen a él, excepto (a lo sumo) el lugar por el que entramos y el lugar por el que salimos. El motivo es que cada vez que llegamos a un cruce y volvemos a irnos de él usamos dos caminos, así que, al final, el número total será par, excepto que no hayamos llegado desde ningún sitio (entrada) o bien, nos quedemos allí (salida).

El papel de la vara del explorador es crear un nuevo camino entre dos de los puntos, de forma que podemos volver par dos cruces impares, o al menos cambiar la paridad de un nodo por otro.

En el laberinto que nos ocupa, el lugar de entrada y el de salida están claros (tienen un único camino), pero hay varios puntos más a los que llega un número impar de caminos, que evidentemente serán los que deberemos dejar sin recorrer, ya que no podremos pasar por alguno de ellos.

Vamos al grano. El cruce entre C, D y E, el cruce entre E, G e I, el que hay entre F, G y H y el que hay entre J, H y la Salida tienen 3 caminos, así que tendremos que reducir el número de caminos que llegan a ellos. Como hay un total de cuatro, con la única vara deberemos solucionar el camino entre dos de ellos, y recorrer todos los demás (menos la ruta que lleve de uno a otro) con normalidad.

Estudiando cuál es el camino más barato de suprimir, sería el H, que sólo tiene 3, y entonces la vara se usaría en el camino E, y tendríamos todos los cruces pares. Un recorrido de este estilo podría ser A-B-C-D-F-G-E-E-I-J.

No sirve de nada suprimir los caminos D y F, ya que no hay manera de añadir una única vara y volver pares los dos cruces restantes, por lo que las demás soluciones que quedan son variantes de la que ya hemos dicho.

La puntuación total que podemos conseguir es de 39, por lo tanto.