Programozás‎ > ‎Feladatok‎ > ‎

Legrövidebb út mátrixban

Egy n x n -es mátrix bal felső sarkából a jobb alsó sarkába szeretnénk eljutni úgy, hogy az út során érintett mezőkre írt számok összege minimális legyen. Egy mezőről az élszomszédos mezőkre lehet lépni. A mátrix elemei pozitív egész számok. 

Feladat

Írjunk programot, ami megadja a minimális összegű útvonalon szereplő számok összegét.

Bemenet

A bemenet egy 80 x 80 -as mátrix. 80 sor, mindegyikben 80 szám, vesszővel elválasztva.

Kimenet

Egyetlen szám, a minimális összeg.

Példa

Bemenet  Kimenet
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
2297


Tesztadatok

p083_matrix.txt         425185

Címkék

A feladat forrása: Project Euler 83-as feladat, https://projecteuler.net/problem=83
Algoritmusok: legrövidebb utak

megoldás