Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-02-17 19:52:04.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	semafoare.in, semafoare.out	Sursă	Algoritmiada 2010, Runda 3
Autor	Paul-Dan Baltescu	Adăugată de	Paul-Dan Baltescu •pauldb
Timp execuţie pe test	0.175 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Semafoare

Laura traieste in orasul Simplu. Harta orasului Simplu este de forma unui grid de dimensiuni N si M, unde strazile sunt reprezentate de liniile gridului. Asadar, orasul are (N+1)*(M+1) intersectii. Fata cunoaste faptul ca in fiecare intersectie se afla un semafor, care functioneaza in felul urmator: la minutul t pot intra in intersectie doar masinile aflate fie spre nord, fie spre est, fie spre sud sau cele dinspre vest. Daca la minutul t intra in intersectie masinile aflate spre nord, atunci la minutul t+1 pot intra doar masinile aflate spre est, la t+2 intra cele dinspre sud, la t+3, cele dinspre vest, la t+4 intra din nou cele dinspre nord si asa mai departe. Odata intrata in intersectie o masina isi poate continua drumul mai departe sau poate vira spre stanga sau spre dreapta. Laura mai cunoaste faptul ca timpul necesar pentru a parcurge cu masina o strada aflata intre doua intersectii consecutive este de 1 minut. Voi veti primi o matrice de caractere A avand N+1 linii si M+1, fiecare element avand o valoare din multimea {'N', 'E', 'S', 'V'}. Fiecare element al matricii A codifica directia dinspre care intra masinile in intersectia corespunzatoare la momentul 0 ( 'N' pentru nord, 'E' pentru est, 'S' pentru sud, 'V' pentru vest). Stiind ca la momentul de timp 0, Laura intra in intersectia (x1, y1) din directia d, determinati timpul minim necesar fetei pentru a ajunge in intersectia (x2, y2) (fara a iesi din oras).

Date de intrare

Pe prima linie a fişierului de intrare semafoare.in se afla doua numere naturale, N si M. Pe a doua linie se afla doua numere intregi si un caracter din multimea {'N', 'E', 'S', 'V'}, separate printr-un singur spatiu, reprezentand x1 y1 d. Pe linia a treia linie se afla alte doua numere intregi separate printr-un spatiu, x2 y2. Pe urmatoarele N+1 linii se afla cate un sir de M+1 caractere din multimea {'N', 'E', 'S', 'V'}, reprezentand matricea A.