Fişierul intrare/ieşire:	semafoare.in, semafoare.out	Sursă	Algoritmiada 2010, Runda 3
Autor	Paul-Dan Baltescu	Adăugată de	Paul-Dan Baltescu •pauldb
Timp execuţie pe test	0.175 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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ş).

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.

Date de ieşire

În fişierul de ieşire semafoare.out se află un singur număr întreg reprezentând timpul minim cerut.

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.

Exemple

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.

Cum se trimit solutii?