Bombetes en un tauler P40953


Statement
 

pdf   zip

thehtml

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++