Glitch y los mundos cerrados

Karel acaba de entrar a NEXUS, el videojuego más esperado del año. Al iniciar sesión aparece su guía del tutorial: una extraña entidad llamada Glitch.

Glitch le explica a Karel que, antes de comenzar la aventura, debe revisar algunos mundos de entrenamiento. En cada mundo hay una frontera marcada con montones de zumbadores. Según Glitch, si la frontera está totalmente cerrada, entonces el mundo está bien sellado; si no lo está, existe un hueco por donde algo podría entrar.

Glitch plantea esto como un simple reto del tutorial. Tu tarea es ayudar a Karel a decidir si la frontera de zumbadores forma una figura cerrada o si tiene algún extremo abierto.

Problema

El mundo de Karel contiene montones de 1 zumbador que representan la frontera. Dos posiciones de la frontera se consideran adyacentes si comparten un lado.

La frontera del mundo se considera totalmente cerrada si, para cualesquiera dos posiciones ~A~ y ~B~ de la frontera, hay al menos dos formas distintas de moverse entre ellas utilizando únicamente posiciones adyacentes de la frontera.

Tu programa debe hacer lo siguiente:

• si la frontera es totalmente cerrada, debe dejar a Karel orientado al norte;
• si la frontera no es cerrada, debe dejar a Karel orientado al sur.

Entrada

La imagen muestra diferentes ejemplos de frontera. Los primeros dos ejemplos muestran una frontera que no está cerrada. Mientras que los últimos dos muestran ejemplos de fronteras totalmente cerradas.

Consideraciones

• Karel inicia en la posición (1,1) viendo hacia el Norte.
• Karel lleva INFINITOS zumbadores en la mochila.
• La casilla (1,1) no forma parte de la frontera.
• El mundo de Karel es rectangular y no tiene paredes internas.
• Para obtener los puntos de este problema, solo importa la orientación final de Karel.

Subtareas

• ⭐ Subtarea 1 (25 puntos): La frontera es una línea recta o un rectángulo.
• Subtarea 2 (25 puntos): Si la frontera no está cerrada, se te asegura que no se cruza sobre sí misma.
• Subtarea 3 (25 puntos): Las fronteras cerradas forman una figura que nunca se cruza sobre sí misma.
• Subtarea 4 (25 puntos): Sin consideraciones adicionales.