Problem B
Snertu gras

Dómarar að snerta gras.

Keppendurnir sem eru mættir í Forritunarkeppni Framhaldsskólanna eru margir reyndir og hæfir forritarar. En það er eitt sem þessir keppendur gera að meðaltali mun minna af en meðaleinstaklingur og mættu endilega læra að gera oftar. Það er auðvitað, eins og dæmatitill gefur til kynna, að snerta gras.

Til að aðstoða keppendur við að venjast því að snerta gras brúum við hér bilið með því að leyfa ykkur að útbúa forrit sem snýst um að snerta gras. Þá eruð þið vonandi aðeins meira undirbúin undir það að snerta alvöru gras á eftir.

Þið fáið kort af staðsetningu ykkar, veggjum og staðsetningum á grasi. Út frá þessu þurfið þið að finna stystu leið frá núverandi staðsetningu ykkar að næsta grasbletti. Kortið verður rúðustrikað, svo eitt skref er hreyfing frá núverandi reit að reit fyrir norðan, sunnan, vestan eða austan þann reit. Ekki er hægt að fara út af kortinu, það táknar jaðar svæðisins sem er óhætt að fara á. Ekki væri gott að fara snerta of mikið gras og fara venjast þess að vera úti, þá mynduð þið kannski hætta að forrita, sem væri afar slæmt.

Inntak

Inntak byrjar á tveimur heiltölum $h, w$, hæð og breidd kortsins. Gefið er að $h, w \geq 1$ og $h \cdot w \leq 1\, 000\, 000$. Næst fylgja $h$ línur, hver með $w$ stöfum (ásamt nýlínustaf). Þessir stafir verða allir S, ., # eða G. S táknar núverandi staðsetningu þína og mun sá stafur koma fyrir nákvæmlega einu sinni í inntaki. Reitir með grasi eru táknaðir með G, reitir með vegg eru táknaðir með # og auðir reitir með .. Hægt er að færa sig yfir á alla reiti nema þá sem eru með vegg.

Úttak

Ef hægt er að komast á reit með grasi, prentið fjölda skrefa sem það tekur í minnsta lagi. Prentið annars thralatlega nettengdur.

Stigagjöf

Aukaverðlaun

Í hádegishlé þessarar keppni hvetjum við ykkur til að snerta gras. Okkur er svo alvara með þetta að í ár verða aukaverðlaun fyrir það lið sem sendir okkur bestu myndina af sér í keppnisbolunum sínum að snerta gras. Hægt er að senda okkur þá mynd (með liðsnafni) á #jarm á Discord rás okkar, eða á keppnisforritun@gmail.com.

5 5
.....
.##G.
..##.
S..#.
.....

7

5 3
GGG
###
#S#
###
GGG

thralatlega nettengdur