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
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
.128013 ],59/f78rnb _o=ylaepcwgu)vd4613kmhtsP(S0+2[j-i: 050B0t0J0s0U0r0K0m0v0r0s0K0K0p010J0U0u010406050K0y0H0H0s0j0q040N0o0r0y0:0o0k050f0`0|0~100^0u04051g191j0f1g0^0B0U0A0(0*0,0.0I0U0x0I0r1x0I0J0?050Z0l0r0t1s0+0-011w1y1A1y0J1G1I1E0J0j1h0J0I1K1u010g0#0t0k0s0H0t010(130K0u0s0k0.0Q1E1=1@1#1M1(1I1+1-0?0a0m0L0j0o0u0o0K0U160k0m0X1:0j0j0t0v2e191|0k1h0f1Z2r1W1Y1X1F0B1~0.1A0k1*2b1E1p1r0)1L2B0U2D0k0o2H1E0u2k1h2p2r2V0_1?2f2J1$2O0j0}0r0?0m0E2o2Z0@2Y1}2#1M2%2)2+0Q2.1@2:2p2A012^0s2*040m0F2|2q0^2 2?0.32340m0C382~2Z303e2+0d3i3a3k3c310o2(332+0D3p2;2!1t2@3u2_350h3z3b3C3d3E3w350i3I3r3K3t3v3f0e3Q2=3S3m040E0O3i1k2T192H2u0B1Y2z3s0v2P1.1h3,1i3*2X1a2/053=0X2U3R2K010G0?0X0g3(3J440w2+4a432$0g0?0K0o0|0t0n0H2M0U2)4n2{3}2}3A300=040M4f3Y440k0?0x0j0#1I4C3B444z0z0V3p0m4S0m4x3s4F04184v2q4U4b1$0o0?0p3i4$4g2@0l0?214L4y0?4B4!424D2$4G4I0r4K4`4V3S4O4R4T534E0?3=0r172D4,584(4*5f4%1M4z0R4?4W4~4J0t5o540?5n525k3d0?0U5t4N0?0b5w2X5y014p0?3%5x4.0.4z0b5j5O450?0g3u5S4|2@5A5Y4M4(4d042M5$3l4:040j1@0x5s5N5Z5P4^5C4}4Y5{5l0?0z5R4`064T4-5^5U045W0j5,5p040S6c3S0o5)5+4`665%4/0?5:0k5=5~5_4A6t5J0U0?2-5@6n6u0c6g595}6B4@044P56654S5g5!045b5d5?5H5T5m6w5K045M6V675Q6F5h040P4+6l6P5z044H5r6w6X6I3s6Z6#3~5I5Q5G6}5T4X6f6_5u04622V646N6O5I46695X6.5I4X5B7h5T6i5A4Z2V6m5-6p5;6U716%5`75446Z6A6$6C014z6E7l674X7p7w7E4O4Q637b7b6/315a136T6@5v6w7j7Y776)1M4)046-7q7T4X6=507v4w6~7Z7z5|7k7D6J5F7!0?747|3s6(7I7E7*0P7(3d5.4p7L7?6W7y823Z7V5c0k5e7_5 04708e7J5#85307*0T896x6z7$0b7H7-7i8j7X8n6u8q2q7.8t8h5D770z6M6N7T7e6a8y7#8u3s7n5*8d4#7.5.6q6s8I7F8g7M3l0?8%357T8w8y6Z4u8O1$7G8y8_8-7B7$8D2/7r8!0?8x926y3#7$6L7Q7R658M6R7W8l7=8L7@8p7 5*8B905i8Z3Z8b6k8}8o4_9A6:6S9m7$8K4{7E8Y9D8.77952}978i9k8k8m9M6^9M9L968^0?889w7A9c7C8:835E9u6+8X5q7;9H9r7{9,767~8-738B8R9g7c5T7e2k0J0y0j8?9R4E9y8?7T4z9C9`6G9F9Vah8~603z0f400t2r2Sar3+1q3-2u2x2s0s1Hau0f3,0^aE0Y0!0$04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)