Generación de paredes de laberinto de camino más largo

Question

Tengo una cuadrícula 2D de celdas cuadradas adyacentes, con longitud de lado par (siempre existe una celda central)

Cada celda representa un campo de un laberinto o un enigma, que algún "peón" debe "visitar". El peón comienza en el centro y solo puede hacer movimientos horizontales y verticales. Calculo la cantidad mínima posible de esos movimientos. Obviamente, para cualquier laberinto vacío así, sería alguna trayectoria en "espiral" y la cantidad de movimientos sería igual al número de celdas menos uno.

Sin embargo, puedo dibujar "paredes" entre las celdas, prohibiendo movimientos horizontales o verticales, solo si cada celda seguirá siendo visitable. A veces eso puede obligar al peón a visitar algunas celdas dos veces, maximizando el recorrido mínimo.

¿Cómo dibujar paredes de tal manera que la cantidad de movimientos sea máxima? En otras palabras, ¿Cuál es la solución definitiva de paredes para hacer que el recorrido mínimo del peón sea de longitud máxima?

Answer 1

Podemos asumir que dibujamos una colección máxima de paredes: si hay otra pared que podemos dibujar que aún dejará el laberinto conectado, entonces deberíamos dibujar esa pared, y eso solo puede aumentar la longitud del camino máximo.

En ese caso, el laberinto no contiene ciclos: el único tipo de camino que comienza en una ubicación $X$ y regresa a $X$ es un camino que repite cada paso que da.

En particular, un camino que comienza en el centro, visita cada ubicación, y vuelve al centro debe hacer cada movimiento posible dos veces. Si vamos de la ubicación $X$ a una ubicación adyacente $Y$, entonces entramos en un fragmento del laberinto del cual solo podemos salir regresando de $Y$ a $X$.

Si la cuadrícula es $n \times n$, hay $n^2$ celdas, entonces hay $n^2-1$ pares de celdas adyacentes sin pared entre ellas, y por lo tanto necesitamos $2n^2-2$ movimientos para hacer esto. Este número de movimientos siempre es posible: simplemente duplica cada borde y luego realiza un recorrido euleriano.

Si un camino comienza en el centro y visita cada ubicación, pero no regresa al centro, entonces podemos seguirlo con un camino desde la ubicación final hasta el centro, y el resultado debe tener una longitud de al menos $2n^2-2$. Entonces, el camino original debe tener una longitud de al menos $2n^2-2-d$, donde $d$ es la distancia desde el centro hasta su ubicación final.

Además, siempre podemos encontrar un camino que comience en el centro, visite cada ubicación en $2n^2-2-d$ pasos y termine en una celda a $d$ pasos de distancia del centro. Simplemente toma un camino de longitud $d$ desde el centro hasta esa celda, y duplica cada borde que no esté en el camino. Luego, el grafo resultante tiene un camino euleriano desde el centro hasta esa celda de longitud $2n^2-2-d$.

Siempre hay una celda que está al menos a $n-1$ pasos de distancia del centro: una de las esquinas. (La distancia solo puede aumentar cuando agregamos paredes). Entonces, para que el camino mínimo sea lo más largo posible, asegúrate de que cada celda sea accesible en $n-1$ pasos desde el centro; entonces no habrá ningún camino más corto que $2n^2-n-1$.

Hay muchas formas de hacer esto; aquí hay una que es fácil de generalizar.