Županijsko natjecanje 2018. / Osnovna škola (8. razred) - 3. zadatak

Gledajući seriju Igra prijestolja Rebeka je naučila kako se trenira zmaj.

Međutim, njen posao nije treniranje zmajeva već programiranje.

Pomozi Rebeki napisati program koji će odgovoriti na pitanja iz sljedećeg zadataka.

Zadana je tablica s R redaka i S stupaca.

U polja tablice upisana su velika slova engleske abecede i po tim se poljima robot može kretati, te znakovi „#“ koji predstavljaju nepremostive prepreke za robota.

Pored tablice zadana je riječ K.

Robot na put kreće s prohodnog polja u X-tom retku i Y-tom stupcu, a može se kretati prema gore, dolje, lijevo i desno.

Kreće se izvršavajući slijed naredbi koji mu je zadan („U“ - gore, „D“ - dolje, „L“ - lijevo, „R“ - desno) i koji ponavlja svaki put kada dođe do zadnje naredbe iz slijeda.

Ako bi robot u nekom koraku izvršavajući trenutnu naredbu udario u prepreku ili izašao iz tablice, tada preskače tu naredbu i prelazi na sljedeću.

Ako ne može izvršiti niti jednu naredbu završava svoje putovanje.

Robot ima riječ koja je na početku prazna.

Nakon što se pomakne na neko polje dodaje slovo koje je napisano na tom polju na kraj svoje riječi.

Primijetite da je prvo slovo njegove riječi ono koje je na polju na koje se robot prvo pomakne, a ne na polju iz kojeg kreće.

Napiši program koji će na osnovi ulaznih podataka odgovoriti na sljedeća pitanja:

1. Kako izgleda robotova riječ nakon točno 10 pomaka?
2. Nakon koliko je najmanje pomaka robot, od prikupljenih slova, mogao dobiti riječ K, na način da izbaci neka slova (moguće nijedno) iz svoje riječi u tom trenutku? Npr. ako je nakon šest pomaka njegova riječ “ABACBC”, onda je mogao složiti riječ “ACC”, tako da izbaci drugo, treće i peto slovo iz te riječi.
3. S kojeg polja bi robot trebao krenuti da bi odgovor na drugo pitanje bio minimalan? Ako je više takvih polja ispiši ono s najmanjom oznakom retka, a ako je i dalje više takvih onda ono s najmanjom oznakom stupca.

Garantiramo da će robot moći napraviti barem 10 pomaka ako krene s polja u X-tom retku i Y-tom stupcu i da će odgovor na drugo pitanje biti prirodan broj manji ili jednak 100.

ULAZNI PODATCI

U prvom retku nalaze se prirodni brojevi R i S (2 ≤ R, S ≤ 10), brojevi iz teksta zadatka.

U sljedećih R redaka nalazi se po S znakova koji opisuju tablicu iz zadatka.

U sljedećem retku nalaze se prirodni brojevi X i Y (1 ≤ X ≤ R, 1 ≤ Y ≤ S), brojevi iz teksta zadatka.

U sljedećem retku nalazi se riječ sastavljena od znakova „U“, „D“, „L“, „R“ i ne dulja od 100 znakova, slijed naredbi kretanja iz teksta zadatka.

U sljedećem retku nalazi se riječ K iz teksta zadatka. Riječ K sastavljena je od najviše 20 znakova i sadrži samo velika slova engleske abecede.

IZLAZNI PODATCI

U prvi redak treba ispisati niz od 10 znakova, odgovor na prvo pitanje iz teksta zadatka.

U drugi redak treba ispisati prirodan broj, odgovor na drugo pitanje iz teksta zadatka.

U treći redak treba ispisati dva prirodna broja, redom oznaku retka i stupca polja koje je odgovor na treće pitanje iz teksta zadatka.

PRIMJERI TEST PODATAKA

Ulaz

3 3
GAB
C#A
AAA
1 1
RDDRRDDLLDUU
BABA

Izlaz

ABAAAACGAB
11
1 2

Objašnjenje

Opis prvog primjera: Robot je na početku na poziciji (1, 1) i njegova riječ je prazna.

Prvo se pomakne desno, sada je njegova riječ “A”.

Nakon toga se 2 puta pokušava pomaknuti prema dolje, no ne može jer ga sprječava prepreka, no može se pomaknuti desno te je sada, nakon drugog pomaka, njegova riječ “AB”.

Nakon toga se miče desno pa je njegova riječ “ABA”. Nakon 10 pomaka ima riječ “ABAAAACGAB”.

Nakon 11 pomaka riječ je “ABAAAACGABA” te sada može dobiti riječ “BABA” tako da ostavi samo drugo, treće, deseto i jedanaesto slovo.

Ako krene s pozicije (1, 2) može dobiti riječ “BABA” u 10 koraka, što je najmanje moguće.

Ulaz

2 5
BCAB#
#####
1 1
RRRLLL
BAC

Izlaz

CABACBCABA
5
1 3

Ulaz

3 3
##A
AAA
##A
2 1
RRUD
AA

Izlaz

AAAAAAAAAA
2
1 3