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

Laura trăieşte în oraşul Simplu. Harta oraşului Simplu este de forma unui grid de dimensiuni $N$ şi $M$, unde străzile sunt reprezentate de liniile gridului. Aşadar, oraşul are $(N+1)*(M+1)$ intersecţii şi vom nota cu $(i, j)$ intersecţia dintre cea de a $i$-a stradă orizontală cu cea de a $j$-a stradă verticală. Fata cunoaşte faptul că în fiecare intersecţie se află un semafor, care funcţionează în felul următor: într-un minut oarecare $t$, pot intra în intersecţie doar maşinile aflate fie spre nord, fie spre est, fie spre sud, fie spre vest. Dacă la minutul $t$ intră în intersecţie maşinile aflate spre nord, atunci la minutul $t+1$ pot intra maşinile aflate spre est, la $t+2$ intra cele dinspre sud, la $t+3$, cele dinspre vest, la $t+4$ intră din nou cele dinspre nord, etc. Odată intrată în intersecţie o maşină îşi poate continua drumul mai departe sau poate vira spre stânga sau spre dreapta. Laura mai cunoaşte faptul că timpul necesar pentru a parcurge cu maşina o stradă aflată între două intersecţii consecutive este de $1$ minut. Voi veţi primi o matrice $A$ avand $N+1$ linii si $M+1$ coloane, fiecare element fiind un caracter din mulţimea ${'N', 'E', 'S', 'V'}$. Fiecare element al matricii $A$ codifică direcţia din care intră maşinile în intersecţia corespunzătoare în minutul $0$ ( $'N'$ pentru nord, $'E'$ pentru est, $'S'$ pentru sud, $'V'$ pentru vest). Ştiind că la momentul de timp $0$, Laura intră în intersecţia $(x1, y1)$ din direcţia $d$, determinaţi timpul minim necesar fetei pentru a ajunge cu maşina la semaforul din intersecţia $(x2, y2)$ (fără a ieşi din oraş).

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

Pe prima linie a fişierului de intrare $semafoare.in$ se află două numere naturale, $N$ şi $M$. Pe a doua linie se află două numere întregi şi un caracter din mulţimea ${'N', 'E', 'S', 'V'}$, separate câte un singur spaţiu, reprezentând $x1 y1 d$. Pe linia a treia se află alte două numere întregi separate printr-un spaţiu, $x2 y2$. Pe urmatoarele $N+1$ linii se află câte un şir de $M+1$ caractere din mulţimea ${'N', 'E', 'S', 'V'}$, reprezentând matricea $A$.

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$ se află un singur număr întreg reprezentând timpul minim cerut.

În fişierul de ieşire $semafoare.out$ se afla un singur numar intreg reprezentand timpul minim cerut.

h2. Restricţii

* $1 ≤ N, M ≤ 1 000$
* Liniile matricii se consideră numerotate de la $0$ la $N$, iar coloanele de la $0$ la $M$.
* Testele problemei sunt grupate două câte două. Pentru fiecare grupă, unul dintre teste este disponibil pentru evaluarea parţială. (50% dintre teste sunt disponibile pentru evaluarea parţială.)
* În timpul cerut nu intră în considerare timpul pe care Laura îl petrece aşteptând la semaforul din intersecţia destinaţie.

* $1 ≤ N ≤ 1 000$
* 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. Exemple

h2. Exemplu

table(example). |_. semafoare.in |_. semafoare.out |
| 3 4

ESNSS
SSNSE
VVNSE

| 7
|
| 5 5
0 5 S
3 1
ENSVVN
VNENVN
NEESEE
ENSSNE
SVVVNS
NESSNS
| 19
|
 
 

| 13
|

h3. Explicaţie

Pentru primul exemplu, Laura va parcurge drumul descris în continuare pentru a ajunge în timp minim la destinaţie. La minutul $0$, Laura se află la semaforul din intersecţia $(1, 1)$ venind dinspre nord. Ea aşteaptă $2$ minute pentru a intra în intersecţie şi consumă $1$ minut pentru a ajunge în intersecţia $(1, 2)$. Ea intră în intersecţia $(1, 2)$ în minutul $3$ (deoarece acum vine dinspre est) şi mai consumă $1$ minut pentru a ajunge în intersecţia $(2, 2)$. Ea nu aşteaptă nici la acest semafor şi intră în intersecţie în minutul $4$, iar apoi porneşte spre intersecţia $(2, 3)$. Fata nu aşteaptă nici un minut nici în intersecţia $(2, 3)$ (deoarece vine dinspre vest) şi porneşte spre intersecţia $(3, 3)$. Ajunge în intersecţia $(3, 3)$ în minutul $6$ şi porneşte spre $(3, 4)$ chiar în acelaşi minut. Laura ajunge la semaforul din intersecţia destinaţie în minutul $7$.

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") ==

4542