Državno natjecanje 2014. godine za 1. i 2. razred Srednje Škole - 3. zadatak - 2. dan

Zmija leži na kvadratnoj mreži od R redaka i S stupaca, retci su označeni brojevima od 1 do R odozgo prema dolje, stupci brojevima od 1 do S s lijeva na desno. Tijelo zmije je niz različitih kvadratića kvadratne mreže od kojih su svaka dva uzastopna u nizu međusobno susjedna u mreži (imaju zajednički brid).

Dodatno, zmija je sklupčana ulijevo, točnije ako se krećemo po kvadratićima od repa do glave onda u svakom trenutku ili idemo ravno ili skrećemo ulijevo. Drugim riječima, ako se krećemo po kvadratićima od repa do glave, i trenutna pozicija je usred nekog kvadratića tako da smo leđima okrenuti prema kvadratiću iz kojeg smo došli, onda je dozvoljeno kretanje ili na kvadratić ravno naprijed ili na kvadratić lijevo. Također, zmija ne siječe samu sebe, odnosno putem od repa do glave prođemo kroz svaki zauzeti kvadratić mreže točno jednom.

Poznati su kvadratići koje zmija zauzima te lokacija repa i glave. Napišite program koji će odrediti jedan mogući način na koji zmija leži, odnosno ispisati redom kvadratiće koji čine njeno tijelo počevši od repa pa sve do glave.

ULAZNI PODACI

U prvom redu nalaze se dva prirodna broja R i S (1 ≤ R, S ≤ 100), broj redaka i broj stupaca kvadratne mreže.

U svakom od sljedećih R redova nalazi se niz od točno S znakova. Znakovi mogu biti ‘.’ (točka), malo slovo ‘x’, veliko slovo ‘R’ ili velikog slovo ‘G’. Točka označava prazan kvadratić kvadratne mreže, a ‘x’ kvadratić na kojem se nalazi tijelo zmije.

U kvadratnoj mreži će uvijek biti točno jedno veliko slovo ‘G’ koje označava glavu zmije, i točno jedno veliko slovo ‘R’ koje označava rep zmije.

IZLAZNI PODACI

Potrebno je ispisati N redova gdje je N broj kvadratića koji nisu označeni znakom ‘.’ u ulazu. U svakom redu treba ispisati dva prirodna broja RK i SK (1 ≤ RK ≤ R, 1 ≤ SK ≤ S), redak i stupac jednog kvadratića koji sadrži tijelo zmije. Tijelo zmije mora biti opisano redom od repa prema glavi, drugim riječima R1, S1 moraju biti koordinate kvadratića koji u ulazu sadrži ‘R’, RN, SN moraju biti koordinate kvadratića koji u ulazu sadrži ‘G’, a redovi između opisuju redom put od glave do repa koji prolazi kroz svaki kvadratić označen znakom ‘x’ u ulazu točno jednom te u svakom koraku ide ravno ili skreće ulijevo. Napomena: Rješenje će uvijek postojati, ali ne mora biti jedinstveno.

PRIMJERI TEST PODATAKA

ulaz

5 6
......
.xxxx.
.x.Gx.
.xxxx.
...Rx.

izlaz

5 4
5 5
4 5
3 5
2 5
2 4
2 3
2 2
3 2
4 2
4 3
4 4
3 4

ulaz

4 4
R...
x.G.
xxx.
....

izlaz

1 1
2 1
3 1
3 2
3 3
2 3

ulaz

3 6
xxxxxx
xGxxRx
xxxxxx

izlaz

2 5
3 5
3 6
2 6
1 6
1 5
1 4
1 3
1 2
1 1
2 1
3 1
3 2
3 3
3 4
2 4
2 3
2 2