Somme minimale (2)
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 :pbv(40i2+edm3s7= 1jo5w_lSnatf-)9h]6,crg[yPku8/ 050m0l0D0C0i0z0p0s0M0z0C0p0p0r010D0i0c010406050p0T0n0n0C0N0Q040A0v0z0T0:0v0B050V0`0|0~100^0c04191g051j0V1j1l1g0^0m0i0e0(0*0,0.0I0i0O0I0z1z0I0D0?050Z0d0z0l1u0+0-011y1A1C1A0D1I1K1G0D0d0v0m101H0N1h0D0I0(130p0c0C0B0.0j011M1w010E0#0l0B0C0n0l1G1.1:1^1O1{1K1~200?0a0s0R0N0v0c0v0p0i160B0s0X1,0N0N0l0M2l19230B1h0V1*2y0D1(1%1)0m250.1C0B1}2i1G1r1t0)1N2I0i2K0B1!1s1G0c2r1h2w2y2$0_1/2m2Q1_2V0N0}0z0?0s0t2v2*0@2)242,1O2.2:2=0j2^1:2`2w2H012 0C2;040s0o332x0^362}0.393b0s0g3f352*373l2=0w3p3h3r3j380v2/3a2=0K3w2{2+1v2~3B303c0q3G3i3J3k3L3D3c0U3P3y3R3A3C3m0H3X2|3Z3t040t0h3p1i2!192O2B0m2F370M1!211h3?1k3;2(1a2_053{0X2#3Y2R010S0?0X0E3/3Q4a0x2=4g492-0E0?0p0v0|0l0y0n2T0i2:4t3243343H370=040f4l3)4a0B0?0O0N0#1K4I3I4a4F0G0b3w0s4Y0s4D3z4L04184B2x4!4h1_0v0?0r3p4,4m2~0d0?284R4E0?4H4*484J2-4M4O0z4Q504#3Z4U4X4Z594K0?3{0z172K4=5e4.4:5l4-1O4F0P4|4$544P0l5u5a0?5t585q3k0?0i5z4T0?0J5C2(5E014v0?3.5D4@0.4F0J5p5U4b0?0E3B5Y522~5G5(4S4.4j042T5,3s4_040N1:0O5y5T5)5V4~5I534(615r0?0G5X50064Z4?5~5!045$0N5=5v040u6i3Z0v5/5;506c5-4^0?5_0B5{645 4G6z5P0i0?2@5}6t6A0L6m5f636H4}044V5c6b4Y5m5*045h5j5|5N5Z5s6C5Q045S6#6d5W6L5n040k4;6r6V5F044N5x6C6%6O3z6)6+445O5W5M735Z4%6l6 5A04682$6a6T6U5O4c6f5%6@5O4%5H7n5Z6o5G4)2$6s5?6v5`6!776-607b4a6)6G6,6I014F6K7r6d4%7v7C7K4U4W697h7h6^385g136Z6}5B6C7p7(7d6/1O4/046?7w7Z4%6{567B4C747)7F627q7J6P5L7*0?7a823z6.7O7K7:0k7.3k5@4v7R7|6$7E883*7#5i0B5k7 6504768k7P5+8b377:0F8f6D6F7,0J7N7?7o8p7%8t6A8w2x7@8z8n5J7d0G6S6T7Z7k6g8E7+8A3z7t5:8j4+7@5@6w6y8O7L8m7S3s0?8-3c7Z8C8E6)4A8U1_7M8E8 8?7H7,8J2_7x8*0?8D986E3,7,6R7W7X6b8S6X7$8r7{8R7}8v855:8H965o8)3*8h6q938u4 9G6_6Y9s7,8Q517K8(9J8@7d9b349d8o9q8q8s9S6~9S9R9c8~0?8e9C7G9i7I8_895K9A6;8%5w7`9N9x819=7c848?798H8X9m7i5Z7k2r0D0T0N8|9X4K9E8|7Z4F9Ia06M9L9#an94663G0V460l2y2Zax3=1s3@2B2D2z1Z1#2B0C1JaA0V3?0^aN0Y0!0$04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)