Programozás‎ > ‎Feladatok‎ > ‎

Játék (OKTV)

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 <= N, M <= 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

Bemenet  Kimenet
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

Címkék

A feladat forrása: NTOITV 2011. 2. forduló, 11-13. évfolyam
Algoritmusok: 

megoldás