== include(page="template/taskheader" task_id="semafoare") ==
Poveste şi cerinţă...
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).
h2. Date de intrare
Fişierul de intrare $semafoare.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $semafoare.out$ ...
În fişierul de ieşire $semafoare.out$ se afla un singur numar intreg reprezentand timpul minim cerut.
h2. Restricţii
