Diseño de Laberintos

A Peter le encanta dibujar laberintos, y recientemente tuvo una idea: ¿cuál sería la cantidad mínima de movimientos necesarios de la pluma para dibujar un laberinto, siempre comenzando y terminando en la misma posición? Para hacer el juego más interesante, Peter decidió que no se le permite levantar la pluma del papel. Las plantillas para la construcción del laberinto son siempre cuadradas, 3 x 3, 4 x 4, 5 x 5 hasta un máximo de 7 x 7.

Para cada ejemplo, Peter debe especificar dónde se debe comenzar el dibujo y su tarea es determinar la cantidad de movimientos necesarios para dibujar el laberinto de Peter. Peter te recuerda que no tienes que preocuparte por los ciclos, porque no habrá ciclos en ninguno de los casos de prueba. Sin embargo, un caso de prueba puede tener una entrada 4 1 y otra entrada 1 4. Esto significa dos líneas que conectan estos mismos dos nodos. De todos modos no hará ninguna diferencia en el dibujo del laberinto porque la cantidad de movimiento debe ser igual.

Mira el siguiente ejemplo, en el laberinto A (4 x 4), Peter quiere comenzar en el nodo 0, dibujar todas las líneas y regresar al nodo 0. Para esto, el mínimo de movimientos posibles es 30. En el laberinto B (3 x 3), Pedro empieza en el nodo 1, dibuja todas las líneas y regresa al nodo 1. En este caso, necesita 10 movimientos para realizar este dibujo.