Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-02-18 15:58:37.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:semafoare.in, semafoare.outSursăAlgoritmiada 2010, Runda 3
AutorPaul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.175 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Semafoare

In momentul in care trimiti o sursa, vei putea vedea scorul obtinut pe o parte din testele folosite la evaluare in monitor.

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 ≤ 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ă.)

Exemplu

semafoare.insemafoare.out
3 4
1 1 N
3 4
NSEVV
ESNSS
SSNSE
VVNSE
13

Explicaţ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). În intersecţia (1, 2) ea aşteaptă până în minutul 5 (deoarece acum vine dinspre est) şi mai consumă 1 minut pentru a ajunge în intersecţia (3, 1). Ea aşteaptă la acest semafor până în minutul 7 şi apoi se deplasează 1 minut spre intersecţia (2, 3). În minutul 10 ea intră în intersecţie (dinspre nord) şi porneşte spre intersecţia (2, 4). Aşteaptă 1 minut la semafor şi în minutul 12 pleacă spre intersecţia (3, 4). Drumul durează 1 minut şi Laura ajunge la semaforul destinaţie din intersecţia (4, 3) în minutul 13. Acesta este unul dintre drumurile minime posibile pe care poate merge Laura.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?