Quants camins? P84609


Statement
 

pdf   zip

thehtml

Considereu una matriu n × m, on a cada casella (i, j) hi ha un nombre xij que indica que es pot saltar cap avall a una distància (en nombre de caselles) entre 1 i xij, ja sigui verticalment, en diagonal cap a l’esquerra, o en diagonal cap a la dreta. Si anomenem (0, 0) la posició de dalt a l’esquerra, totes les caselles visitades han de tenir coordenades entre 0 i n per a les files (això inclou una fila per sota de l’última), i entre 0 i m − 1 per a les columnes. L’objectiu és començar a la fila 0, i arribar exactament a la fila n. Quants camins hi ha?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, m, i n files amb m naturals. Suposeu que tant n, com m, com els xij estan entre 1 i 100.

Sortida

Per a cada cas, escriviu el nombre de camins que comencen a qualsevol casella de la fila de dalt i acaben a qualsevol casella just a sota de la fila de baix, mòdul 109 + 7.

Public test cases
  • Input

    1 1
    1
    
    1 3
    1 1 1
    
    2 3
    1 1 1
    1 1 1
    
    5 1
    99
    99
    99
    99
    99
    
    3 4
    3 7 6 3
    1 2 4 2
    5 1 2 9
    

    Output

    1
    7
    17
    16
    110
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++