Llenando con baldosas P73138


Statement
 

pdf   zip

thehtml

Dado un tablero n × m con c casillas ya marcadas, tenéis que acabar de llenarlo con baldosas 1 × 2, cada una de las cuales se puede poner horizontalmente o verticalmente.

Entrada

La entrada consiste en diversos casos. Cada caso empieza con n, m y c, seguidos de c pares diferentes (x, y) indicando las casillas inicialmente llenas. Podéis suponer que n · m está entre 2 y 45, que el número de casillas inicialmente vacías es par, y que las filas y columnas se numeran a partir de cero.

Salida

Para cada caso, escribid el número de maneras de acabar de llenar la matriz.

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
    Spanish
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++