Més camins en un tauler (2) P81810


Statement
 

pdf   zip

thehtml

Considereu un tauler n × m amb alguns obstacles. Compteu tots els camins que surten de la cantonada superior esquerra, arriben a la cantonada inferior dreta, i passen exactament per sobre de k obstacles. Els únics moviments permesos són cap avall i cap a la dreta.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, m i k, seguits d’n línies amb m ‍caràcters cadascuna. Els punts indiquen posicions lliures, i les ‘X’ obstacles. Podeu assumir que n i m estan entre 2 i 100, i que k està entre 0 i n + m − 1.

Sortida

Per a cada cas, escriviu el nombre de camins possibles. Com que aquest nombre pot ser molt gros, feu els càlculs mòdul 109 + 7.

Public test cases

  • Input

    2 2 3
XX
.X

3 4 0
.X..
...X
X...

3 4 4
.X..
...X
X...

11 35 45
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

    Output

    1
2
0
481256764
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++