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

== include(page="template/detailed-feedback" 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ş).
h2. Date de intrare

h2. Restricţii

* $1 ≤ N ≤ 1 000$

* $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.

h2. Exemplu

h2. Exemple

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

SSNSE
VVNSE
| 7

|

| 5 5
0 5 S
3 1

4542