Egy n × n-es pálya mezőin kell a lehető legtöbb pontot összegyűjteni. A bal felső sarokból indulunk, a jobb alsóban van a cél, lefele, jobbra és átlósan lehet lépni.
Feladat
Írjunk programot, ami megadja a szerezhető összpontszám maximumát, és kiír egy olyan útvonalat, ami maximális pontszámot eredményez!
Bemenet
A bemenet első sora n értékét tartalmazza (2 <= n <= 100). Ezután n sorban n darab szám következik, a mezőkön megszerezhető pontok értéke. (0 <= pont <= 9)
Kimenet
A kimenet első sorába a maximálisan szerezhető pontszámot kell írni, a másodikba pedig egy maximális pontszámot adó útvonal kódját.
Az útvonal JJLLALJ... alakban van megadva, ahol J a jobbra, L a lefele, A pedig az átlósan lefele történő lépést jelöli.
Példa
| Bemenet |
Kimenet |
4
0 2 2 8
1 5 1 7
4 9 5 6
1 9 1 5
|
32
JLLJJL
|
Tesztadatok
Címkék
A feladat forrása: saját feladat, írásbeli fordulók gyakori feladattípusa.
Algoritmusok: dinamikus programozás
megoldás | 
2004-2016 BDG algoritmus szakkör