== include(page="template/taskheader" 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 in intersectia $(x2, y2)$ (fara a iesi din oras).

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

h2. Restricţii
* $... ≤ ... ≤ ...$

* Liniile matricii se considera numerotate de la $0$ la $N$, iar coloanele de la $0$ la $M$.
* Testele problemei sunt grupate doua cate doua. Pentru fiecare grupa, unul dintre teste este disponibil pentru evaluarea partiala. (50% dintre teste sunt disponibile pentru evaluarea partiala).

h2. Exemplu
table(example). |_. semafoare.in |_. semafoare.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 4
1 1 N
3 4
NSEVV
ESNSS
SSNSE
VVNSE
| 13

|
h3. Explicaţie

...

La minutul $0$, Laura se afla la semaforul din intersectia $(1, 1)$ venind dinspre nord. Ea asteapta $2$ minute pentru a intra in intersectie si consuma $1$ minut pentru a ajunge in intersectia $(1, 2)$. In intersectia $(1, 2)$ ea asteapta pana la momentul de timp $5$ (deoarece acum vine dinspre est) si mai consuma $1$ minut pentru a ajunge in intersectia $(3, 1)$. Ea asteapta la acest semafor pana in minutul $7$ si apoi se deplaseaza $1$ minut spre intersectia $(2, 3)$. In minutul $10$ ea intra in intersectie (dinspre nord) si porneste spre intersectia $(2, 4)$. Asteapta $1$ minut la semafor si in minutul $12$ pleaca spre intersectia $(3, 4)$. Drumul dureaza $1$ minut si Laura ajunge la semaforul din intersectia $(4, 3)$ destinatie in minutul $13$. Acesta este unul dintre drumurile minime posibile pe care poate merge Laura.

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