Školsko natjecanje 2013. / Osnovna škola (8. razred) - 2. zadatak

Pazi: test podaci za ovaj zadatak su krivi. Potrebno ih je ponovno postaviti

Poznati arheolog i pustolov Dr. Henry Walton, bolje nam znan kao Indiana Jones Jr., našao se pred novim izazovom.

Ovoga puta u potrazi je za starim majanskim blagom te ga još samo nekoliko koraka dijeli od njega.

Potrebna mu je vaša pomoć.

Indiana se nalazi u prostoriji pravokutnog oblika čiji pod možemo podijeliti na kvadratne ploče jednake veličine.

Prostorija je prepuna zamki koje se kriju ispod ploča, no srećom Indiana se domogao uputa koje mu pokazuju kako se sigurno kretati prostorijom.

Upute se sastoje od niza znakova koji mogu biti ‘S’, ‘I’, ‘J’ ili Z’. Ti znakovi označavaju stranu svijeta prema kojoj se treba pomaknuti (S – sjever ili jedno mjesto iznad trenutnog mjesta na kojemu se nalazi, I – istok ili jedno mjesto desno, J – jug ili jedno mjesto dolje, Z – zapad ili jedno mjesto lijevo).

Uz upute za kretanje Indiana je pronašao i kartu prostorije koja se sastoji od znakova za koje zna da imaju sljedeće značenje:

• znak ‘.’ - obična ploča;
• veliko slovo ‘B’ - ploča ispod koje se nalazi blago;
• znamenka (0 - 9) - kada se Indiana nañe na ovoj ploči treba preskočiti onoliko idućih uputa za kretanje koliki se broj nalazi na tom polju.

Iako je Indiana poznat po svojoj neustrašivosti, ovog puta odlučio je malo razmisliti prije nego se upusti u novu pustolovinu.

Zanima ga koliko blaga može iskopati na putu opisanom u uputama (jednom kad Indiana iskopa blago ispod neke ploče, više ga ne može iskopati na istom mjestu).

Na početku Indiana se nalazi u sjeverozapadnom kutu prostorije, na najgornjoj lijevoj kvadratnoj ploči.

Ulazni podaci

U prvom retku nalazi se jedan prirodan broj K (1 ≤ K ≤ 20), broj znakova u uputama za kretanje.

U drugom retku nalazi se string duljine K koji predstavlja upute za kretanje.

U trećem retku nalaze se dva prirodna broja N i M (1 ≤ N, M ≤ 8), redom brojevi redaka i stupaca prostorije.

U svakom od idućih N redaka nalazi se po M znakova koji predstavljaju kartu prostorije koju je Indiana dobio.

Napomena: za natjecatelje u Basicu, znakovi su složeni jedan ispod drugog.

Napomene:

• ulazni podaci bit će takvi da upute nikada neće voditi izvan prostorije;
• u sjeverozapadnom kutu karte (otkuda Indiana polazi) uvijek će biti obična ploča.

Izlazni podaci

U jedinom retku treba ispisati koliko blaga Indiana može iskopati na putu opisanom u uputama.

Primjeri test podataka

Ulaz

3
IJI
3 3
...
BBB
.B.

Izlaz

2

Ulaz

6
JISSIJ
3 3
...
B2.
BBB

Izlaz

2

Objašnjenje

Pojašnjenje drugog test primjera: pomak prema dolje (iskopano blago), pomak udesno, preskočena iduća dva znaka, pomak udesno, pomak prema dolje (iskopano blago).

Ulaz

13
IJIIJISIZSZJJ
5 5
.B..B
.2...
BB1B2
...1B
.B...

Izlaz

4