Vasile a "imprumutat" o masina si a plecat in oras sa se distreze.
Ghinionul a fost ca masina apartinea politiei si era dotata cu un echipament
care emitea semnale indicand directia de miscare a masinii.
Politistii au luat imediat harta orasului si, cunoscand pozitia initiala a masinii
si directiile de miscare, vor sa determine pozitia finala a masinii.
Harta orasului este de forma dreptunghiulara, pe ea fiind marcate cu '.' (punct)
pozitiile prin care masinile pot circula, iar cu 'X' pozitiile prin care masinile
nu pot circula. Pozitia initiala a masinii a fost marcata pe harta cu '*'. Masina
se poate deplasa in 4 directii la nord (adica mai sus), la sud (mai jos), la
vest (adica la stanga) sau la est (la dreapta).
Cerinta
Scrieti un program care sa ajute politistii sa gaseasca masina.
Date de intrare
Pe prima linie a fisierului de intrare masina2.in
se gasesc doua numere naturale separate prin spatiu R
C, unde R reprezinta
numarul de linii, iar C
numarul de coloane de pe harta orasului.
Fiecare dintre urmatoarele R
linii contine o secventa de C
caractere care pot fi doar '.',
'*' sau 'X',
descriind harta orasului.
Urmatoarea linie (a (R+2)-a)
contine un numar natural N
reprezentand numarul de schimbari de directie pe care le-a facut masina.
Fiecare dintre urmatoarele N
linii contine un sir de caractere care poate fi (NORD,
SUD, VEST
sau EST). Evident, oricare
doua directii consecutive sunt diferite.
Date de iesire
Fisierul de iesire masina2.out
contine harta orasului reprezentata ca in fisierul de intrare (R
linii de cate C caractere).
Pe harta vor fi marcate cu '*'
numai pozitiile finale posibile ale masinii.
Restrictii
1 <= R, C <= 50
1 <= N <= 1000
Exemple
masina2.in
masina2.out
3 4
....
*..X
X.X.
2
EST
NORD
.**.
...X
X.X.
masina2.in
masina2.out
10 9
........X
X..XX..X.
.X.XX.X..
...XX....
...XX....
.XXX..XX.
.......X.
..XXX.X..
X.X....X.
*.....X..
4
EST
NORD
EST
SUD