Somme minimale pour traverser un carré

Une grille carrée étant donnée, remplie d'entiers positifs, on souhaite traverser le carré avec une somme minimale des entiers rencontrés.

Pour cet exercice,

• on souhaite aller du côté gauche au côté droit,
• les seuls déplacements autorisés sont →, ↓, ↑

\[\begin{pmatrix} 131 & 673 & \mathbf{234} & \mathbf{103} & \mathbf{18} \\ \mathbf{201} & \mathbf{96} & \mathbf{342} & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331\\ \end{pmatrix}\]

Le chemin marqué en gras donne une somme de \(994\) qui est ici le minimum possible pour cet exercice.

Écrire une fonction telle que somme_minimale_2(grille) renvoie la somme minimale spécifiée plus haut. On garantit que la grille est carrée et remplie d'entiers positifs.

Exemples

\[\begin{pmatrix} 5 & 2 & 3 \\ \mathbf 2 & \mathbf 0 & 2 \\ 3 & \mathbf 2 & \mathbf 1 \\ \end{pmatrix}\]

🐍 Console Python

>>> grille = [[5, 2, 3], [2, 0, 5], [3, 2, 1],]
>>> somme_minimale_2(grille)
5

\[\begin{pmatrix} 9 & 9 & 0 & 9 & 9 \\ \mathbf{3} & \mathbf{1} & 9 & 9 & 9 \\ 5 & \mathbf{1} & 9 & \mathbf{1} & \mathbf{3} \\ 7 & \mathbf{1} & 9 & \mathbf{1} & 9\\ 9 & \mathbf{1} & \mathbf{1} & \mathbf{1} & 9\\ \end{pmatrix}\]

🐍 Console Python

>>> grille = [
...     [9, 9, 0, 9, 9],
...     [3, 1, 9, 9, 9],
...     [5, 1, 9, 1, 3],
...     [7, 1, 9, 1, 9],
...     [9, 1, 1, 1, 9],
... ]
>>> somme_minimale_2(grille)
14

\[\begin{pmatrix} 131 & 673 & \mathbf{234} & \mathbf{103} & \mathbf{18} \\ \mathbf{201} & \mathbf{96} & \mathbf{342} & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331\\ \end{pmatrix}\]

🐍 Console Python

>>> grille = [
...     [131, 673, 234, 103, 18],
...     [201, 96, 342, 965, 150],
...     [630, 803, 746, 422, 111],
...     [537, 699, 497, 121, 956],
...     [805, 732, 524, 37, 331],
... ]
>>> somme_minimale_2(grille)
994

###

Lancer # testsbksl-nlbksl-nlgrille = [[5, 2, 3], [2, 0, 5], [3, 2, 1]]bksl-nlassert sommepy-undminimalepy-und2(grille) == 5bksl-nlbksl-nlbksl-nlgrille = [bksl-nl [9, 9, 0, 9, 9],bksl-nl [3, 1, 9, 9, 9],bksl-nl [5, 1, 9, 1, 3],bksl-nl [7, 1, 9, 1, 9],bksl-nl [9, 1, 1, 1, 9],bksl-nl]bksl-nlassert sommepy-undminimalepy-und2(grille) == 14bksl-nlbksl-nlbksl-nlgrille = [bksl-nl [131, 673, 234, 103, 18],bksl-nl [201, 96, 342, 965, 150],bksl-nl [630, 803, 746, 422, 111],bksl-nl [537, 699, 497, 121, 956],bksl-nl [805, 732, 524, 37, 331],bksl-nl]bksl-nlassert sommepy-undminimalepy-und2(grille) == 994bksl-nlbksl-nlbksl-nldef secretpy-undsommepy-undminimalepy-und2(grille):bksl-nl n = len(grille)bksl-nl colonne = [grille[i][0] for i in range(n)]bksl-nl for j in range(1, n):bksl-nl colonne[0] += grille[0][j]bksl-nl for i in range(1, n):bksl-nl colonne[i] = grille[i][j] + min(colonne[i - 1], colonne[i])bksl-nl for i in range(n - 2, -1, -1):bksl-nl colonne[i] = min(colonne[i], colonne[i + 1] + grille[i][j])bksl-nl return min(colonne)bksl-nlbksl-nlbksl-nlfrom random import randrangebksl-nlbksl-nlfor n in [1, 2, 3, 4, 5, 6, 7, 8, 16, 32, 64]:bksl-nl grille = [bksl-nl [bksl-nl randrange(10py-strpy-str6) py-str (i + 3) py-str (j + 3) py-str (n + 3 - i) py-str (n + 3 - j)bksl-nl for j in range(n)bksl-nl ]bksl-nl for i in range(n)bksl-nl ]bksl-nl attendu = secretpy-undsommepy-undminimalepy-und2(grille)bksl-nl resultat = sommepy-undminimalepy-und2(grille)bksl-nl assert attendu == resultatbksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def sommepy-undminimalepy-und2(grille):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlgrille = [[5, 2, 3], [2, 0, 5], [3, 2, 1]]bksl-nlassert sommepy-undminimalepy-und2(grille) == 5bksl-nlbksl-nlbksl-nlgrille = [bksl-nl [9, 9, 0, 9, 9],bksl-nl [3, 1, 9, 9, 9],bksl-nl [5, 1, 9, 1, 3],bksl-nl [7, 1, 9, 1, 9],bksl-nl [9, 1, 1, 1, 9],bksl-nl]bksl-nlassert sommepy-undminimalepy-und2(grille) == 14bksl-nlbksl-nlbksl-nlgrille = [bksl-nl [131, 673, 234, 103, 18],bksl-nl [201, 96, 342, 965, 150],bksl-nl [630, 803, 746, 422, 111],bksl-nl [537, 699, 497, 121, 956],bksl-nl [805, 732, 524, 37, 331],bksl-nl]bksl-nlassert sommepy-undminimalepy-und2(grille) == 994bksl-nlbksl-nldef sommepy-undminimalepy-und2(grille):bksl-nl n = len(grille)bksl-nl colonne = [grille[i][0] for i in range(n)]bksl-nl for j in range(1, n):bksl-nl colonne[0] += grille[0][j]bksl-nl for i in range(1, n):bksl-nl colonne[i] = grille[i][j] + min(colonne[i - 1], colonne[i])bksl-nl for i in range(n - 2, -1, -1):bksl-nl colonne[i] = min(colonne[i], colonne[i + 1] + grille[i][j])bksl-nl return min(colonne)bksl-nlbksl-nl

A

Z