Bombetes en un tauler P40953


Statement
 

pdf   zip

html

Considereu un tauler amb n × m bombetes. Algunes han d’estan apagades, algunes enceses, i d’algunes se’n pot escollir l’estat. A més, sabem quantes bombetes exactament han d’estar enceses a cada fila i a cada columna. Feu un programa per comptar totes les combinacions coherents amb les restriccions donades.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m. Segueixen n files amb m caràcters cadascuna. Una ‘X’ indica una bombeta que ha d’estar apagada, una ‘O’ una bombeta que ha d’estar encesa, i un punt una bombeta de la qual es pot triar l’estat. Segueixen els n comptadors de bombetes enceses a cada fila, i els m comptadors de bombetes enceses a cada columna. Podeu suposar 1 ≤ n · m ≤ 100.

Sortida

Per a cada tauler, escriviu de quantes maneres es poden complir totes les restriccions. Amb els jocs de proves donats, aquest nombre sempre estarà entre 1 i 106.

Public test cases
  • Input

    1 3
    X.O
    2
    0 1 1
    
    2 4
    ....
    ....
    2 2
    1 1 1 1
    
    3 4
    ..XO
    OOXX
    ....
    3 2 2
    2 2 1 2
    
    4 4
    ....
    ....
    ....
    ....
    1 1 1 1
    1 1 1 1
    

    Output

    1
    6
    1
    24
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++