Somme minimale pour traverser un carré en diagonale
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 coin supérieur gauche au coin inférieur droit,
- les seuls déplacements autorisés sont →, ↓
\[
\begin{pmatrix}
\mathbf{131} & 673 & 234 & 103 & 18 \\
\mathbf{201} & \mathbf{96} & \mathbf{342} & 965 & 150 \\
630 & 803 & \mathbf{746} & \mathbf{422} & 111 \\
537 & 699 & 497 & \mathbf{121} & 956 \\
805 & 732 & 524 & \mathbf{37} & \mathbf{331}\\
\end{pmatrix}
\]
Le chemin marqué en gras donne une somme de \(2427\) qui est ici le minimum possible pour cet exercice.
Écrire une fonction telle que somme_minimale_1(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}
\mathbf{1} & \mathbf{5} & 9 \\
10 & \mathbf{3} & 5 \\
10 & \mathbf{2} & \mathbf{3}
\end{pmatrix}
\]
🐍 Console Python
>>> grille = [[1, 5, 9], [10, 3, 5], [10, 2, 3]]
>>> somme_minimale_1(grille)
14
\[
\begin{pmatrix}
\mathbf{131} & 673 & 234 & 103 & 18 \\
\mathbf{201} & \mathbf{96} & \mathbf{342} & 965 & 150 \\
630 & 803 & \mathbf{746} & \mathbf{422} & 111 \\
537 & 699 & 497 & \mathbf{121} & 956 \\
805 & 732 & 524 & \mathbf{37} & \mathbf{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_1(grille)
2427
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 ]x,59/f.78rnb _o=ylaepcwgu)vd4613kmhtsP(S0+2[j-i: 050D0v0L0u0W0t0M0o0x0t0u0M0M0r010L0W0w010406050M0A0J0J0u0l0s040P0q0t0A0=0q0m050g0|0~10120`0w04051i1b1l0g1i0`0D0W0C0*0,0.0:0K0W0z0K0t1z0K0L0^050#0n0t0v1u0-0/011y1A1C1A0L1I1K1G0L0l1j0L0K1M1w010h0%0v0m0u0J0v010*150M0w0u0m0:0S1G1@1_1%1O1*1K1-1/0^0a0o0N0l0q0w0q0M0W180m0o0Z1=0l0l0v0x2g1b1~0m1j0g1#2t1Y1!1Z1H0D200:1C0m1,2d1G1r1t0+1N2D0W2F0m0q2J1G0w2m1j2r2t2X0{1^2h2L1(2Q0l0 0t0^0o0G2q2#0_2!1 2%1O2)2+2-0S2:1_2=2r2C012`0u2,040o0H2~2s0`312^0:34360o0E3a302#323g2-0e3k3c3m3e330q2*352-0F3r2?2$1v2_3w2{370j3B3d3E3f3G3y370k3K3t3M3v3x3h0f3S2@3U3o040G0Q3Z3D2M3V3H0G2/1c2;3s3!3,3$0G2}3;2 1m2V1b2J2w0D1!2B3u0x2R1:1j411k3 2Z3|2s05470Z2W3T3,0I0^0Z0h3k3C320y2-4r3L3^0h0^0M0q0~0v0p0J2O0W2+4E3:2Z4x1(0@040O4w4l2(0^0z0l0%1K4S3@4O0^0B0X3r0o4+0o4s3u0m0^1a4f374.3U0q0^0r3k4-4N2_0n0^234!3+4$4Q543n4V4X0t4Z4?4^3,4P0B4*4,5f4U044B4D0M4}5l1O4`044|4?4~4T1O4P0T0b5j4+5s3f0^0x0}0A0t5r4 0:5u5w2X5y4#1O4G0^3)4?064,5T551O4n040h3w5N5z5H040c5-5U5P4u042O5=5%5/4W4Y0v583u5B613U5W045Y4M5.014P0b4)5Z5#5#5G335I5K5M5x6i5u0R5R2;5$595:5E6g6i4:5n4C1/5q5e5O015u0i643^0^0u0w0w1,0D6J564R6E6a6z5J0J5L6R5A4%6w6i5)5+0l5{6u0W6,3u0q5^5`6n6F0m51040l1_0z606U5?6b0^6T6971664L2;6i4P0d6/3#4;6!0:5h6e2X5!6g5F6^4A6B0v6D755|72040T7g016668796F6c7d3,5Q7F5m5o6C7y63707u7A7M0^5D6@6a6p7I2_5a5 7R7w7y6z6.7O326c7x7*3u7Q7.3U7E6f7m6t3u6)5,7U716z0U7X5@0^6?5S6y6`6|0m6~7#747C6a777#7c7}7u6z4=7t7+4%7j3=7^6x7o6A5p7#7-8m4/0^807;5g7S816G4{8F6z5~5c6 8y7=0^8x8d7~837#0b8Q3}8t8B8N8D047T856F7W8i3n6`4G8l8R7u4P8c8X6V7p8v8C568W4g8Y8U8h8(8^8u7L8{6#7$965/8Z6s6o0^0V8F8f997v0b5i7@7n6a5)2m0L0A0l8/2 7_7e947r8w7y5u9f9i9h8!568%3=1b4i0v2t2U9M401s422w2z2u0u1J9P0g410`9Z0!0$0(04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)