NézetNyomtat

Játék (Megoldás)
Címkék > Feladat
Elmélet > Algoritmusok > Gráfalgoritmusok

Játék

Tekintsük azt az egyszemélyes játékot, amelyet egy $N$ sorból és $M$ oszlopból álló négyzet­rácsos táblán lehet játszani! A tábla véletlenszerűen kiválasztott mezőin gyöngyöket helyez­nek 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éksza­bá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él­mező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ön­gyö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 kez­deti 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$ ka­raktert tartalmazzon, egy olyan szabályos lépéssorozatot, amellyel elérhető a maximális pont­szá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.BEJATEK.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