Problème
Commencez dans le coin supérieur gauche d'une grille comportant rows lignes et columns colonnes de cases. Déplacez-vous uniquement le long des arêtes des cases, d'une case à la fois, soit vers la droite, soit vers le bas, jusqu'à atteindre le coin inférieur droit. Comptez le nombre de séquences de déplacements distinctes. La grille ne contient aucun obstacle.
Une grille de 2 lignes et 3 colonnes nécessite exactement 2 déplacements vers le bas et 3 vers la droite.
Implémentez lattice_paths(rows, columns).
Entrée
rows : Le nombre de lignes de cases, et non de sommets.
columns : Le nombre de colonnes de cases, et non de sommets.
Sortie
Retournez le nombre d'itinéraires du coin supérieur gauche au coin inférieur droit.
Contraintes
0 ≤ rows, columns ≤ 30 et rows + columns ≤ 60. Zéro dans une dimension donne un chemin direct. Une grille 0 × 0 possède un unique chemin vide. Les résultats tiennent dans un entier signé 64 bits.
Exemples
Entrée :
rows = 2
columns = 3
Sortie attendue :
expected = 10Entrée :
long long rows = 2;
long long columns = 3;
Sortie attendue :
long long expected = 10;Entrée :
long rows = 2;
long columns = 3;
Sortie attendue :
long expected = 10;Explication
Chaque itinéraire comporte cinq déplacements. Choisir lesquels sont les deux déplacements vers le bas donne dix itinéraires distincts.
Entrée :
rows = 0
columns = 4
Sortie attendue :
expected = 1Entrée :
long long rows = 0;
long long columns = 4;
Sortie attendue :
long long expected = 1;Entrée :
long rows = 0;
long columns = 4;
Sortie attendue :
long expected = 1;Explication
Il n'existe que le chemin direct composé de quatre déplacements vers la droite.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Chaque chemin n’est qu’un ordre possible des mouvements vers le bas et vers la droite requis.
Indice 2
Compte combien de façons il y a de choisir les positions d’un type de mouvement parmi tous les mouvements, plutôt que d’explorer les chemins un par un.
Indice 3
Fais attention aux grilles dégénérées : si une dimension vaut zéro, il existe exactement un chemin tout droit, et une grille 0×0 a aussi un seul chemin vide.
Complexité attendue
temps O(min(rows, columns)), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.