== include(page="template/taskheader" task_id="semafoare") ==

== include(page="template/detailed-feedback" task_id="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 la *semaforul* din intersectia $(x2, y2)$ (fara a iesi din oras).
h2. Date de intrare