Planificació urbanística P61630


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • Input

    3 4
    ????
    ?C?.
    ???.
    
    1 10
    .C.....???
    
    2 2
    ??
    ??
    
    1 1
    ?
    
    2 29
    ?.?.?.?.?.?.?.?.?.?.?.?.?.?.?
    C.C.C.C.C.C.C.C.C.C.C.C.C.C.C
    

    Output

    ....
    .C..
    ....
    
    ...C
    .C..
    ....
    
    ----------
    .C........
    
    .C.......C
    
    .C......C.
    
    .C.....C..
    
    .C.....C.C
    
    ----------
    ..
    ..
    
    ..
    .C
    
    ..
    C.
    
    .C
    ..
    
    C.
    ..
    
    ----------
    .
    
    C
    
    ----------
    .............................
    C.C.C.C.C.C.C.C.C.C.C.C.C.C.C
    
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python