Caminar i saltar P87501


Statement
 

pdf   zip

thehtml

Donat un mapa n × m amb obstacles, de quantes maneres es pot anar des de la casella superior esquerra fins a la casella inferior dreta? Només es pot caminar (moure’s a la casella immediatament a la dreta o avall), o saltar (moure’s a la casella dues posicions a la dreta o avall, però només si enmig hi ha un obstacle). No es pot passar mai per cap obstacle.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m, seguits de n files amb m caràcters. Les posicions ocupades tenen una ‘X’, i les buides un punt. Les caselles inicial i final sempre estan buides. Podeu suposar que tant n com m estan entre 2 i 100.

Sortida

Per a cada cas, escriviu el nombre de maneres diferents d’anar des de l’inici fins al final, segons s’ha explicat anteriorment. Com que aquest nombre pot ser molt gros, feu els càlculs mòdul 108 + 7.

Public test cases
  • Input

    2 3
    ...
    ...
    
    3 6
    .X...X
    .XX...
    .X....
    
    10 35
    ...................................
    ...................................
    ...................................
    ...................................
    ...................................
    ...................................
    ...................................
    ...................................
    ...................................
    ...................................
    

    Output

    3
    7
    63921960
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++