Játék
Tekintsük azt az egyszemélyes játékot, amelyet egy
$N$ sorból és
$M$ oszlopból álló négyzetrácsos táblán lehet játszani! A tábla véletlenszerűen kiválasztott mezőin gyöngyöket helyeznek el. A táblán lehetnek csapda mezők, amelyekre nem lehet lépni. A játék célja az, hogy a játékos egy bábut mozgatva a tábla mezőin a lehető legtöbb gyöngyöt gyűjtse be. A játékszabály a következő:
- Kezdetben a bábu a tábla $(1,1)$ koordinátájú bal felső sarkában áll.
- Egy lépésben a bábut csak szomszédos mezőre lehet mozgatni, vagy jobbra, vagy lefelé.
- Csapda mezőre nem lehet lépni.
- A játék akkor ér véget, ha a bábu a tábla $(N,M)$ koordinátájú jobb alsó mezőjére, a célmezőre kerül.
- A játékban szerzett pontszám azokon a mezőkön található gyöngyök számának összege, amelyekre a bábuval lépett a versenyző. Az $(1,1)$ nem csapdamező és az ott lévő gyöngyök is a játékosé lesznek.
Feladat
Készíts programot (JATEK.PAS, ...), amely kiszámít egy olyan játékmenetet, amely a legtöbb pontot eredményezi!
Bemenet
A JATEK.BE szöveges állomány első sora a tábla sorainak $N$, és oszlopainak $M$ számát tartalmazza $(1\leq N, M\leq 150)$, egy szóközzel elválasztva. Az állomány következő $N$ sora a kezdeti játékállást tartalmazza. Minden sorban pontosan $M$ pozitív egész szám van (egy-egy szóközzel elválasztva). Ha $j$-edik szám $-1$, akkor ott csapda mező van, egyébként azt adja meg, hogy az adott sorban a $j$-edik mezőn hány gyöngy van. Minden szám értéke nem nagyobb, mint 500.
Kimenet
A JATEK.KI szöveges állomány első sorába a szabályos játékkal elérhető legnagyobb pontszám értékét kell írni! Ha a célmező nem érhető el, akkor az első és egyetlen sorba a $-1$ értéket kell írni! Ha el lehet jutni a célmezőre, akkor a második sor pontosan $N+M-2$ karaktert tartalmazzon, egy olyan szabályos lépéssorozatot, amellyel elérhető a maximális pontszám! A jobbra lépés jele a 'J', a lefelé lépés jele az 'L' karakter. A karakterek között nem lehet szóköz, és az utolsó karakter után nem lehet szóköz! Több megoldás esetén bármelyik megadható.
Példa
| JATEK.BE | JATEK.KI |
5 6
1 2 3 4 0 1
2 -1 2 1 -1 3
-1 0 6 0 0 0
4 1 0 -1 1 -1
0 0 1 2 0 0
|
17
JJLLLLJJJ
|
Tesztadatok
