Omplint amb rajoles P73138


Statement
 

pdf   zip

thehtml

Donat un tauler n × m amb c caselles ja marcades, cal acabar d’omplir-lo amb rajoles 1 × 2, cadascuna de les quals es pot posar horitzontalment o verticalment.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, m i c, seguits de c parells diferents (x, y) indicant les caselles inicialment plenes. Podeu suposar que n · m està entre 2 i 45, que el nombre de caselles inicialment buides és parell, i que les files i columnes es numeren a partir de zero.

Sortida

Per a cada cas, escriviu el nombre de maneres d’acabar d’omplir la matriu.

Public test cases
  • Input

    1 2 0
    
    2 2 0
    
    2 2 2
    1 1
    0 1
    
    2 2 2
    0 1
    1 0
    
    5 8 0
    
    9 5 1
    0 0
    

    Output

    1
    2
    1
    0
    14824
    30305
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++