Revizia anterioară Revizia următoare
| 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 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).
Date de intrare
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.
Date de ieşire
În fişierul de ieşire semafoare.out se afla un singur numar intreg reprezentand timpul minim cerut.
Restricţii
- 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).
Exemplu
| semafoare.in | semafoare.out |
|---|---|
| 3 4 1 1 N 3 4 NSEVV ESNSS SSNSE VVNSE | 13 |
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.
