Sense tres en ratlla P12999

Graphic problem

Considereu un tauler rectangular n × m, on cada casella té una fitxa amb un d’aquests cinc colors possibles: ‘DodgerBlue’, ‘Lime’, ‘Magenta’, ‘Red’, i ‘White’. Aquí, direm que un tauler és maco si no té tres o més fitxes del mateix color adjacents horitzontalment o verticalment (el que habitualment es coneix com a tres en ratlla). Fixeu-vos que sí que permetem els tres en ratlla en diagonal.

Donat un tauler amb alguns colors ja fixats, decidiu la resta de colors perquè el resultat sigui maco. Si hi ha més d’una solució, trieu aquella lexicogràficament més petita: si identifiqueu cada color amb la seva lletra inicial, i recorreu el tauler per columnes, d’esquerra a dreta, i les columnes de dalt a baix, la paraula obtinguda ha de ser la primera en ordre alfabètic. Com a il·lustració, el tauler solució del segon exemple d’entrada és ‘DLDDDLLDDWLDDDLDDL’.

Entrada

L’entrada consisteix en n i m, seguides de la descripció del tauler: m files amb n caràcters cadascuna. Els punts indiquen posicions per decidir. Els altres caràcters indiquen la inicial d’un color ja fixat: ‘D’, ‘L’, ‘M’, ‘R’, o ‘W’.

Sortida

Cal generar una imatge (50n, 50m) de color de fons ‘Black’ amb el tauler maco més petit possible en ordre lexicogràfic. Teniu la garantia que sempre n’hi haurà almenys un. Cada cel·la ha de ser un quadrat d’amplada 50. Pinteu cada fitxa amb un cercle del seu color, d’amplada 40, i centrat a la seva cel·la.