Cada semana, como ya es costumbre, Boris publica algo en su LinkedIn. Como su fiel seguidor, corres a reaccionar a su última entrada, pero al acceder a la página descubres un juego en la plataforma que capta tu atención.
El juego se desarrolla en una cuadrícula bidimensional de \(n\) filas y \(m\) columnas, y tu objetivo es colocar reinas sobre el tablero siguiendo estas reglas:
- No puede haber más de una reina en la misma fila.
- No puede haber más de una reina en la misma columna.
- Dos reinas no pueden estar en celdas adyacentes, ni horizontal, ni vertical, ni diagonalmente.
- Cada región debe contener exactamente una reina.
Dada la cuadrícula inicial, tu tarea es resolver el juego, en el caso de que sea posible.
Entrada
Un número indeterminado de líneas, que representa el tablero. La región en la que se encuentra cada cuadrícula se define por el caracter que contiene: si dos celdas contienen el mismo caracter, pertenecen a la misma región.
Se garantiza que todas las líneas tendrán la misma longitud y estarán compuestas por caracteres alfanuméricos.
Salida
Imprime "POSIBLE", si existe una configuración válida. En caso contrario, imprime "IMPOSIBLE".
En el caso de que sea posible, imprime cualquier configuración válida.
Para imprimir la configuración del tablero, marca con 'X' las casillas que contienen una reina y las demás con el caracter de su región.