Fişierul intrare/ieşire:robotel.in, robotel.outSursăONI 2016 clasa a 6-a
AutorMircea RotarAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.3 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Roboțel (clasa a 6-a)

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.

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.

Î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.

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.

Cerinţe

Scrieţi un program care, cunoscând numărul R de linii şi coloane şi cele K căsuţe semnalizator, determină:

  1. Toate perechile blocante de pe tablă;
  2. Numărul de paşi efectuaţi pe fiecare sens în parte: Nord, Est, Sud şi Vest.

Date de intrare

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.

Date de ieşire

  • 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 L1 C1 L2 C2 va fi afişată înaintea perechii L3 C3 L4 C4 dacă L1 < L3 sau L1 = L3 şi C1 < C3, 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.

Restricţii

  • 2 ≤ R ≤ 200 şi 1 ≤ KR 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!

Exemplu

robotel.inrobotel.outExplicaţ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)
Trebuie sa te autentifici pentru a trimite solutii. Click aici