Ainsi, le 9 sur la troisième ligne, deuxième colonne, indique que le bloc de coordonnées (i, j) = (2, 1) a une richesse de mine[2][1] = 9. De façon générale, dans la notation mine[i][j], idésigne l'indice de la ligne etjcelui de la colonne.
On garantit que la mine possède au moins une ligne et deux colonnes.
Afin de ne pas user prématurément sa pioche, Steve ne souhaite pas creuser l'intégralité de la mine. À chaque niveau, il envisage plutôt de creuser soit :
↙️ vers le bas à gauche,
⬇️ vers le bas,
↘️ vers le bas à droite.
Lorsque Steve creuse un bloc, il récupère la richesse de celui-ci. Ainsi, en partant du bloc de gauche de la première ligne et en creusant toujours sous ses pieds, il gagnerait un total de \(7+5+8+7+6+3=36\).
Attention
Lorsqu'il atteint le fond de la mine (la dernière ligne de la grille), Steve trouve sous ses pieds une roche sombre incassable : il ne peut plus creuser !
Il se demande donc quel est le meilleur filon à explorer : quelles richesses cumulées maximales peut-il espérer accumuler en creusant à partir de chacun des points de la surface et surtout, parmi celles-ci, laquelle est la meilleure ?
La figure suivante met en évidence un des chemins de richesse cumulée maximale. Elle vaut \(10+7+7+6+6+10=46\).
Son raisonnement est le suivant : " Si je suis en un bloc précis, la richesse cumulée maximale que je peux obtenir à partir de ce bloc est égale à la somme :
de la richesse de ce bloc,
et de la richesse maximale d'un des trois blocs inférieurs que je peux explorer. "
Afin de résoudre ce problème, on fournit une fonction dimensions renvoyant un tuple formé de la hauteur et de la largeur de la "mine" :
🐍 Script Python
defdimensions(mine):"""Renvoie le tuple (hauteur, largeur) de la mine"""returnlen(mine),len(mine[0])
On pourra utiliser cette fonction en faisant : hauteur, largeur = dimensions(mine).
Écrire la fonction meilleure_richesse_cumulee :
prenant comme paramètre la mine (liste de listes),
et renvoyant la plus grande richesse cumulée que l'on peut obtenir à partir d'un des blocs de la surface.
La fonction calculera de façon itérative les richesses cumulées de chaque niveau ien commençant par le bas de la mine et en remontant vers la surface. Ces valeurs seront stockées dans la liste richesses_cumulees.
A chaque étape, on calculera les richesses d'un niveau à l'aide des valeurs de richesses cumulées du niveau du dessous. Ces calculs se feront dans une liste temporaire temp. On parcourra alors les colonnes j en prenant soin de traiter séparément les colonnes de gauche et de droite de la mine (certains des voisins du niveau inférieur sont alors absents).
Une fois les calculs de la nouvelle ligne terminés, on remplacera la valeur de richesses_cumulees par celle de temp avant d'aborder une nouvelle ligne.
La fonction calculera donc les richesses cumulées depuis le fond de la mine et en remontant ligne par ligne vers la surface.
En dernier lieu, elle renverra la valeur maximale des richesses cumulées du niveau 0.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)