Planificació urbanística P61630

Considereu una urbanització en construcció amb n × m parcel·les. Segons la normativa, no hi poden haver cases en parcel·les adjacents (horitzontalment, verticalment o en diagonal). Segons el projecte actual, d’algunes parcel·les ja s’ha decidit si han de tenir una casa o no, i d’altres encara no se sap. Feu un programa que escrigui tots els mapes finals coherents amb el projecte.

Entrada

L’entrada consisteix en diversos projectes. Cada projecte comença amb n i m, seguit d’n files amb m caràcters cadascuna. Una ‘C’ indica una parcel·la que ha de tenir casa, un punt una parcel·la que no ha de tenir casa, i un interrogant una parcel·la per decidir. Podeu suposar que n i m estan entre 1 i 100, que cada projecte té entre 1 i 15 interrogants, i que tots els projectes tenen almenys un mapa final possible.

Sortida

Per a cada projecte, escriviu en ordre lexicogràfic tots els mapes possibles. Per ordenar-los, suposeu que els recorreu per files de dalt a baix, i cada fila d’esquerra a dreta. Tingueu en compte que un ‘.’ va abans que una ‘C’. Escriviu una línia buida després de cada mapa, i una línia amb 10 guions al final de tots els mapes d’un projecte.