Županijsko natjecanje 2013. / Osnovna škola (7. razred) - 3. zadatak

Lucija za zadaću iz informatike treba napraviti pojednostavljenu verziju igrice Snake. Profesor će zadati početno stanje igrice i poteze koje zmija treba napraviti, a njezin program mora prikazati konačno stanje igrice.

Igrica je zadana tablicom stanja koja ima \(N\) redaka i \(M\) stupaca te je popunjena s \(4\) vrste znakova: . - slobodno mjesto, X - mjesto koje zauzima zmijino tijelo, # - mjesto na kojem se nalazi prepreka i * - mjesto na kojem se nalazi hrana.

Potezi su predstavljeni stringom duljine \(P\) koji se sastoji od \(3\) vrste znakova: L - okretanje glave ulijevo, D - okretanje glave udesno i R - nema okretanja glave.

U početnom stanju zmija zauzima jedno polje i glava joj je okrenuta prema desnom kraju tablice. Zmija se zatim pomiče u skladu sa zadanim potezima. Kada je na nekom potezu, zmija ovisno o vrsti znaka, okreće ili ostavlja glavu u istom smjeru, a zatim se pokuša pomaknuti na sljedeće polje - polje prema kojem je okrenuta glava. Ako se uspješno pomakne prelazi na idući potez, inače igra završava.

Kada zmija dođe na polje sa hranom, pojede ju i pritom poraste. Tijelo joj se produži tako da rep ostaje gdje je bio, a glava se pomakne na polje na kojem je bila hrana. Ta hrana sada više ne postoji. Kada zmijino tijelo (rep) napusti neko mjesto, ono postaje slobodno.

Igra završava kada se odrade svi potezi ili u slučaju da se zmija ne može pomaknuti na sljedeće polje. To se događa: kada se na sljedećem polju nalazi prepreka, kada je sljedeće polje izvan tablice (oko tablice nalazi se zid) ili kada se na sljedećem polju nalazi zmijino tijelo.

Kada igra završi, Lucija preostale poteze (ako ih ima) mora zanemariti i ispisati konačno stanje. Budući da nije sigurna kako bi to sama napravila, traži pomoć!

Ulazni podaci

U prvom retku nalaze se dva prirodna broja: \(N\) \((1 \leq N \leq 20)\), broj redaka i \(M\) \((1 \leq M \leq 20)\), broj stupaca početne tablice stanja.

U sljedećih \(N\) redaka nalazi se po \(M\) znakova koji opisuju početni izgled tablice stanja.

U sljedećem retku nalazi se jedan prirodan broj \(P\) \((1 \leq P \leq 100)\), broj zadanih poteza.

U posljednjem retku nalazi se string duljine \(P\) koji opisuje poteze koje zmija treba napraviti.

Izlazni podaci

U svakom od \(N\) redova treba ispisati \(M\) znakova koji prikazuju konačni izgled tablice stanja.

Bodovanje

U test primjerima vrijednim \(36\) bodova zmija nikad neće pojesti hranu - neće rasti. U test primjerima vrijednim \(18\) bodova zmija će pojesti točno jednu hranu.

Primjeri test podataka

Ulaz

4 5
.....
.X*..
.....
..#..
6
DLRDLL

Izlaz

.....
..*..
....X
..#..

Objašnjenje

Pojašnjenje prvog test primjera: Prikazano je stanje igrice po potezima.

Ulaz

6 5
X...#
#*.#.
#..*.
#*#*.
#..#.
#*..#
9
RDRLRDLRD

Izlaz

....#
#..#.
#.XX.
#*#XX
#..#.
#*..#

Objašnjenje

Pojašnjenje drugog test primjera: Ne uspijeva se izvršiti osmi potez (R) jer bi zmija izašla izvan matrice, zadnji potez se također zanemaruje. Prikazano je stanje igrice po potezima.

Ulaz

5 5
..**.
...X.
.**..
.....
.....
8
LLLRDDDR

Izlaz

..X..
.XX..
.XX..
.....
.....

Objašnjenje

Pojašnjenje trećeg test primjera: Ne uspijeva se izvršiti sedmi potez (D) jer bi zmija udarila u samu sebe, zadnji potez se takoñer zanemaruje. Prikazano je stanje igrice po potezima.