3. Naloga

Labirint


V nekem trenutku Miha odpre oči in ugotovi, da se nahaja sredi labirinta. Ne ve točno, kje v labirintu se nahaja, najde pa v žepu svoj mobilni telefon. Ker ima Miha predplačniški paket, ugotovi, da ima dobroimetja le še za 100 sporočil SMS. Odloči se, da bo za vsak svoj premik za eno polje v labirintu prijateljem poslal sporočilo SMS. Miha v vsakem sporočilu SMS (ki vsebuje le en znak) prijateljem napiše, v katero smer se je trenutno premaknil (S = premaknil sem se v smeri severa, J = v smeri juga, V = vzhoda, Z = zahoda). Čez čas se Miha utrudi hoditi po labirintu in prijateljem pošlje SMS z znakom @. Miha se takrat ustavi in čaka na trenutni poziciji. Mihovi prijatelji pa so si med tempriskrbeli zemljevid labirinta in hočejo Mihu pomagati ugotoviti, kje točno v labirintu se nahaja. Poskušajte jim pri tem pomagati in napišite program, ki prebere opis labirinta in Mihovih premikov ter izpiše vse možne koordinate Mihovega trenutnega položaja.


Na obeh slikah je enak labirint in pot, ki ustreza enakemu zaporedju premikov (tri korake na vzhod, tri na jug, dva na zahod in enega na sever).  Kot vidimo iz slik, je tako zaporedje premikov možno pri dveh različnih začetnih položajih, zato tudi Mihovega sedanjega (končnega) položaja ne moremo enolično določiti.

Vhodni podatki: prva vrstica vhoda vsebuje dve naravni števili h in w (med 3 in 100), ki označujeta velikost labirinta. Labirint ima obliko pravokotne kariraste mreže, sestavljene iz h vrstic in w stolpcev.  V sledečih h vrsticah vhoda je predstavljen labirint v obliki tabele ničel in enic. Ničle označujejo prosta polja v labirintu, enice pa neprehodna polja (zidove). Od (h+2)-ge vrstice naprej pa se po vrsti nahaja vsebina vseh sporočil SMS, ki jih je Miha poslal prijateljem (v vsaki vrstici po eno sporočilo).

Izhodni podatki: program naj izpiše koordinate možnih položajev (v poljubnem vrstnem redu), vsakega v svoji vrstici v obliki x y. Pri tem x pomeni številko stolpca (1 je najbolj levi, w je najbolj desni stolpec), y pa številko vrstice (1 je najbolj zgornja vrstica, h je najbolj spodnja vrstica).

Tvoj program lahko za branje in pisanje uporablja standardni vhod in izhod ali pa datoteke (karkoli ti je lažje).

Primer vhodne datoteke:         Pripadajoča izhodna datoteka:
5 7
0 0 0 0 1 1 1
1 1 0 0 0 0 1
1 0 1 0 1 0 0
1 0 0 0 1 0 1
1 1 1 0 0 0 1
V
V
V
J
J
J
Z
Z
S
@
        2 3
4 4