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 s3o_8bcdufvg/0ly n7apSr1-me,(P2=4:+jtwki9][5h)6 050i0B0L0u0O0p0b0r0h0p0u0b0b0G010L0O0v010406050b0j0A0A0u0x0q040w0d0p0j0:0d0s050n0`0|0~100^0v04191g051j0n1j1l1g0^0i0O0l0(0*0,0.0T0O0m0T0p1z0T0L0?050Z0g0p0B1u0+0-011y1A1C1A0L1I1K1G0L0g0d0i101H0x1h0L0T0(130b0v0u0s0.0F011M1w010k0#0B0s0u0A0B1G1.1:1^1O1{1K1~200?0a0r0E0x0d0v0d0b0O160s0r0X1,0x0x0B0h2l19230s1h0n1*2y0L1(1%1)0i250.1C0s1}2i1G1r1t0)1N2I0O2K0s1!1s1G0v2r1h2w2y2$0_1/2m2Q1_2V0x0}0p0?0r0y2v2*0@2)242,1O2.2:2=0F2^1:2`2w2H012 0u2;040r0c332x0^362}0.393b0r0H3f352*373l2=0S3p3h3r3j380d2/3a2=0V3w2{2+1v2~3B303c0t3G3i3J3k3L3D3c0f3P3y3R3A3C3m0P3X2|3Z3t040y0o3p1i2!192O2B0i2F370h1!211h3?1k3;2(1a2_053{0X2#3Y2R010N0?0X0k3/3Q4a0M2=4g492-0k0?0b0d0|0B0e0A2T0O2:4t3243343H370=040D4l3)4a0s0?0m0x0#1K4I3I4a4F0U0I3w0r4Y0r4D3z4L04184B2x4!4h1_0d0?0G3p4,4m2~0g0?284R4E0?4H4*484J2-4M4O0p4Q504#3Z4U4X4Z594K0?3{0p172K4=5e4.4:5l4-1O4F0R4|4$544P0B5u5a0?5t585q3k0?0O5z4T0?0Q5C2(5E014v0?3.5D4@0.4F0Q5p5U4b0?0k3B5Y522~5G5(4S4.4j042T5,3s4_040x1:0m5y5T5)5V4~5I534(615r0?0U5X50064Z4?5~5!045$0x5=5v040K6i3Z0d5/5;506c5-4^0?5_0s5{645 4G6z5P0O0?2@5}6t6A0C6m5f636H4}044V5c6b4Y5m5*045h5j5|5N5Z5s6C5Q045S6#6d5W6L5n040J4;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:0J7.3k5@4v7R7|6$7E883*7#5i0s5k7 6504768k7P5+8b377:0z8f6D6F7,0Q7N7?7o8p7%8t6A8w2x7@8z8n5J7d0U6S6T7Z7k6g8E7+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?798H8X9m7i5Z7k2r0L0j0x8|9X4K9E8|7Z4F9Ia06M9L9#an94663G0n460B2y2Zax3=1s3@2B2D2z1Z1#2B0u1JaA0n3?0^aN0Y0!0$04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)