Proyecto semanal

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.

12234445
11233445
61111445
66111145
77111141
87111111
88811111
88888111

POSIBLE
12X34445
1123X445
6111144X
X6111145
771111X1
8X111111
88811X11
888X8111

5522000000
5552000000
5555440000
5555440000
5555440000
6666110000
3361111000
3311111100
3331111100
3333111100

POSIBLE
X522000000
555X000000
55554X0000
5555440X00
5555440000
6X66110000
3361X11000
3311111100
33X1111100
3333111100

11
22

IMPOSIBLE