Diferențe pentru problema/robotel între reviziile #2 si #13

Nu există diferențe între titluri.

Diferențe între conținut:

== include(page="template/taskheader" task_id="robotel") ==
Tudor a primit un joc educațional numit “Roboțel” cu ajutorul căruia va învăța punctele cardinale Nord, Est, Sud, Vest. Jocul constă dintr-un roboțel care se deplasează pe o tablă de forma unei matrici pătratice, împărțită în R linii și R coloane. Fiecare căsuță, aflată la intersecția dintre o linie și o coloană, este fie căsuță „liberă”, fie căsuță „semnalizator”, caz în care este etichetată cu una din literele N, E, S, V, reprezentând 4 sensuri posibile de deplasare. Când roboțelul ajunge într-o „căsuță semnalizator”, el își schimbă sensul de deplasare astfel:
- Dacă căsuța este etichetată cu N atunci roboțelul se va deplasa în continuare de jos în sus;
- Dacă căsuța este etichetată cu E atunci roboțelul se va deplasa în continuare de la stânga la dreapta;
- Dacă căsuța este etichetată cu S atunci roboțelul se va deplasa în continuare de sus în jos;
- Dacă căsuța este etichetată cu V atunci roboțelul se va deplasa în continuare de la dreapta la stânga.
Tudor a primit un joc educațional numit “Roboțel” cu ajutorul căruia va învăța punctele cardinale Nord, Est, Sud, Vest. Jocul constă dintr-un roboțel care se deplasează pe o tablă de forma unei matrici pătratice, împărțită în *R* linii și *R* coloane. Fiecare căsuță, aflată la intersecția dintre o linie și o coloană, este fie căsuță „liberă”, fie căsuță „semnalizator”, caz în care este etichetată cu una din literele N, E, S, V, reprezentând 4 sensuri posibile de deplasare. Când roboțelul ajunge într-o „căsuță semnalizator”, el își schimbă sensul de deplasare astfel:
 
* Dacă căsuța este etichetată cu N atunci roboțelul se va deplasa în continuare de jos în sus;
* Dacă căsuța este etichetată cu E atunci roboțelul se va deplasa în continuare de la stânga la dreapta;
* Dacă căsuța este etichetată cu S atunci roboțelul se va deplasa în continuare de sus în jos;
* Dacă căsuța este etichetată cu V atunci roboțelul se va deplasa în continuare de la dreapta la stânga.
 
!>problema/robotel?robotel-1.png!
Două căsuțe semnalizator formează o pereche „blocantă” dacă:
- Se află pe aceeași linie și conțin literele E și V, căsuța cu E are coloana mai mică decât a celei etichetate cu V și între ele, pe aceeași linie nu există alte căsuțe semnalizatoare.
- Se află pe aceeași coloană și conțin literele S și N, căsuța cu S are linia mai mică decât a celei etichetate cu N și între ele, pe aceeași coloană nu există alte căsuțe semnalizatoare.
 
* Se află pe aceeași linie și conțin literele E și V, căsuța cu E are coloana mai mică decât a celei etichetate cu V și între ele, pe aceeași linie nu există alte căsuțe semnalizatoare.
* Se află pe aceeași coloană și conțin literele S și N, căsuța cu S are linia mai mică decât a celei etichetate cu N și între ele, pe aceeași coloană nu există alte căsuțe semnalizatoare.
 
În figura 1, de exemplu, sunt 2 perechi blocante: Perechea (1,2) (5.2) și perechea (2,3) (2,5).
 
Roboțelul pornește din căsuța (1,1), aflată pe prima linie și prima coloană și dacă aceasta este liberă, se deplasează, în cadrul primei linii, de la stânga la dreapta. În cazul în care căsuța de pornire (1,1) este semnalizator, atunci roboțelul se va deplasa pe direcția indicată de litera cu care este etichetată. Considerând că roboțelul se deplasează pe tablă, el se oprește doar în următoarele situații:
- Roboțelul intră într-o căsuță liberă aflată pe prima sau ultima linie, respectiv prima sau ultima coloană, caz în care dacă s-ar menține sensul deplasării actuale roboțelul ar părăsi tabla;
- Roboțelul intră într-o „căsuță semnalizator” a unei perechi blocantă și se va opri în cealaltă căsuță a perechii.
 
* Roboțelul intră într-o căsuță liberă aflată pe prima sau ultima linie, respectiv prima sau ultima coloană, caz în care dacă s-ar menține sensul deplasării actuale roboțelul ar părăsi tabla;
* Roboțelul intră într-o „căsuță semnalizator” a unei perechi blocantă și se va opri în cealaltă căsuță a perechii.
 
!>problema/robotel?robotel-2.png!
De exemplu, în Figura 2, roboțelul ajunge în căsuța liberă (3,5) unde se oprește. În Figura 3, roboțelul se va opri în căsuța (4,1) deoarece dacă ar schimba sensul spre Est, ar reveni în ultima căsuță semnalizator vizitată, (4,3).
Roboțelul înaintează o căsuță într-un pas, în sensul de deplasare.
h2. Cerințe
 
Scrieți un program care, cunoscând numărul *R* de linii și coloane și cele *K* căsuțe semnalizator, determină:
 
# Toate perechile blocante de pe tablă;
# Numărul de pași efectuați pe fiecare sens în parte: Nord, Est, Sud și Vest.
 
h2. Date de intrare
Fișierul de intrare $robotel.in$ ...
Fișierul de intrare $robotel.in$ conține pe prima linie numărul natural *P* reprezentând cerința din problemă care trebuie rezolvată, pe a doua linie, separate printr-un spațiu numărul natural *R* și numărul natural *K*, iar pe următoarele *K* linii, două numere naturale și un caracter, separate prin câte un spațiu reprezentând, în ordine, linia, coloana și litera unei căsuțe semnalizator.
h2. Date de ieșire
În fișierul de ieșire $robotel.out$ ...
* Dacă valoarea lui *P* este 1, se va rezolva doar cerința 1). Fișierul de ieșire $robotel.out$ va conține perechile blocante, pentru fiecare pereche de căsuțe afișându-se 4 numere naturale separate printr-un spațiu, reprezentând, în ordine, linia, coloana primei căsuțe semnalizator, respectiv linia și coloana celei de-a doua căsuțe semnalizator. Perechile de căsuțe vor fi afișate pe linii ordonat după regula: o pereche L[~1~] C[~1~] L[~2~] C[~2~] va fi afișată înaintea perechii L[~3~] C[~3~] L[~4~] C[~4~] dacă L[~1~] < L[~3~] sau L[~1~] = L[~3~] și C[~1~] < C[~3~], adică se va afișa mai întâi perechea cu prima căsuță având linia mai mică decât a primei căsuțe din cealaltă pereche sau la linii egale, va fi afișată perechea cu coloana mai mică. Dacă nu există astfel de perechi de căsuțe, în fișierul de ieșire se va afișa valoarea 0.
 
* Dacă valoarea lui *P* este 2, se va rezolva doar cerința 2). Fișierul de ieșire $robotel.out$ va conține 4 numere naturale separate printr-un spațiu, reprezentând, în ordine, numărul de pași parcurși de roboțel în sensurile Nord, Est, Sud, și Vest.
h2. Restricții
* $... &le; ... &le; ...$
* 2 ≤ *R* ≤ 200 și 1 ≤ *K* ≤ *R* x *R*
* Pentru rezolvarea corectă a fiecărei cerințe se obțin câte 50 de puncte
* O căsuță semnalizator conține o singură literă
* Pentru cerința 2 se garantează că în toate testele deplasarea roboțelului se oprește!
h2. Exemplu
table(example).
|_. robotel.in |_. robotel.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
 
h3. Explicație
 
...
|_. robotel.in |_. robotel.out |_. Explicații |
| 1
5 4
1 3 S
3 1 E
5 1 N
5 3 V
| 0
| Nu există perechi blocante pe tablă care ar putea opri roboțelul.
|
| 1
5 3
1 3 S
4 1 E
4 3 V
| 4 1 4 3
| Perechea blocantă este alcătuită din căsuțele (4,1) cu eticheta E și (4,3) cu eticheta V.
Dacă roboțelul ajunge în una dintre aceste căsuțe, atunci acesta se va opri în cealaltă căsuță.
|
| 1
5 5
1 3 S
2 5 S
4 1 E
4 3 V
5 5 N
| 2 5 5 5
4 1 4 3
| Căsuța semnalizator de pe linia 2, coloana 5 are eticheta S, iar căsuța semnalizator de pe
linia 5, coloana 5 are eticheta N. Dacă roboțelul ajunge în una dintre aceste căsuțe, atunci
acesta se va opri în cealaltă căsuță.
Același lucru se întâmplă pentru căsuța cu litera E de pe linia 4, coloana 1 și căsuța cu
litera V de pe linia 4, coloana 3.
|
| 1
5 5
1 2 S
2 1 E
2 3 E
2 5 V
5 2 N
| 1 2 5 2
2 3 2 5
| Prima pereche blocantă este (1,2) (5.2).
A doua pereche blocantă este (2,3) (2,5). Perechea (2,1) (2,5) nu este validă deoarece conține
un alt semnalizator între ele (vezi figura 1).
|
| 2
5 3
1 3 S
4 1 E
4 3 V
| 0 2 3 2
| Numărul de pași efectuați pe sensul:
Nord: 0 pași
Est: 2 pași în căsuțele (1,2), (1,3)
Sud: 3 pași în căsuțele (2,3), (3,3) (4,3)
Vest: 2 pași în căsuțele (4,2), (4,1)
|
| 2
5 4
1 3 S
3 1 E
5 1 N
5 3 V
| 2 6 4 2
| Numărul de pași efectuați pe sensul:
Nord: 2 pași în căsuțele (4,1), (3,1)
Est: 6 pași în căsuțele (1,2), (1,3), (3,2), (3,3), (3,4), (3,5)
Sud: 4 pași în căsuțele (2,3), (3,3) (4,3), (5,3)
Vest: 2 pași în căsuțele (5,2), (5,1)
|
== include(page="template/taskfooter" task_id="robotel") ==

Nu există diferențe între securitate.