Nombre de chemins dans une grille 2
Imaginons une grille de hauteur
h et de largeur w. L’objectif est de déterminer le nombre de chemins distincts permettant de se déplacer du coin supérieur gauche au coin inférieur droit de la grille. Les seuls déplacements autorisés sont vers la droite, vers le bas et en diagonale vers le coin inférieur droit.o | ➡️ | ㅤ | ㅤ |
⬇️ | ↘ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | x |
Entrée
Les données d’entrée contiennent deux entiers
h et w (1 ≤ h, w ≤ 100).Sortie
Le programme doit afficher le nombre total de chemins uniques pour aller du coin supérieur gauche au coin inférieur droit de la grille. Comme ce nombre peut être très grand, le résultat doit être donné modulo .
Exemples
Input | Output |
2 3 | 5 |
3 4 | 25 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB