Játék
Tekintsük azt az egyszemélyes játékot, amelyet N sorból és M oszlopból álló négyzetrácsos táblán játszanak. A táblán minden mező vagy csapda, vagy valahány gyöngyöt tartalmaz. Egy bábut kell mozgatni a táblán. A bábu kezdetben a tábla bal felső sarkában van, és a jobb alsó sarokba kell eljuttatni az alábbi lépés-szabályt betartva:
- Csak olyan mezőre lehet lépni, ahova még nem lépett a bábu.
- Csapda mezőre nem lehet lépni.
- Csak a négy szomszédos mező valamelyikére lehet lépni.
- Egy lépésben csak jobbra, lefelé, vagy felfelé lehet lépni.
- Minden olyan mezőn levő gyöngy a játékosé lesz, amely mezőre lép.
A játék célja, hogy a játékos a lehető legtöbb gyöngyöt megszerezze.
Feladat
Készíts programot, amely kiszámítja a megszerezhető legtöbb gyöngyök számát, és meg is ad egy olyan lépéssorozatot, amely ezt eredményezi!
Bemenet
A jatek.be szöveges állomány első sorában két egész szám van, a sorok és oszlopok N száma ($1\le N, M\le 100$). A további N sor mindegyike M egész számot tartalmaz egy-egy szóközzel elválasztva. A sorban az i-edik szám a sorban az i-edik mezőn levő gyöngyök száma, ha a szám nemnegatív. Ha a szám -1, akkor az a mező csapda. Minden szám értéke legfeljebb 2000. A bal felső és a jobb alsó mező biztosan nem csapda, és a kiindulási bal felső mezőn levő gyöngyök száma beleszámít az összpontszámba.
Kimenet
A jatek.ki szöveges állomány első sora egy egész számot tartalmazzon, a megszerezhető legtöbb gyöngy számát. Ha nem lehet eljutni a jobb alsó sarokba, akkor a -1 számot kell kiírni, és nem kell második sort írni. Egyébként a második sor olyan "J", "L", "F" betűkből álló lépéssorozatot tartalmazzon, amely legtöbb gyöngyöt eredményez! A második sor szóközöket nem tartalmazhat, és sorvége jellel záruljon. A betűk jelentése: J:jobbra, L: lefelé, F: felfelé.
Példa
| jatek.be | jatek.ki |
5 6
0 0 0 0 -1 0
0 1 0 0 2 0
0 0 -1 1 0 0
3 0 1 0 0 0
0 0 0 0 4 0
|
11
LLLLJFFFJJLLLLJFFFJLLL
|
Tesztadatok
