Programozás‎ > ‎Feladatok‎ > ‎

Kincsvadász

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