Fişierul intrare/ieşire:	agent.in, agent.out	Sursă	ad-hoc
Autor		Adăugată de	CCEX2015 •CCEX2015
Timp execuţie pe test	0.1 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Agent

  Agentul 070 are o nouă misiune. El trebuie să se infiltreze în baza militară a inamicilor lui, unde se află echipamente de ultima generaţie şi invenţii neobişnuite. Ca să îşi îndeplinească misiunea cu succes el trebuie să intre în bază, să extragă toată informţia necesară şi să iasă înainte de a fi capturat. Baza inamicilor săi poate fi reprezentată ca o matrice de nxm elemente. Aliaţii săi au reuşit să îi asigure o cale de intrare în bază în punctele de coordonate xi,yi, informaţiile necesare lui fiind situate în punctul de coordonate xf,yf. Una din invenţiile neobişnuite din acea bază este un dispoziv de teleportare. Odată păşit în unul din aceste aparate agentul nostru ar avea posibilitatea să călătorească oriunde în bază. Dar neavând cunoştinţele necesare ca să programeze coordonatele dorite de el nu le poate folosi pentru teleportare exact lângă punctul de extragere al informaţiei dorite. Din fericire pentru el, aceste dispozitive au memorate în ele coordonate folosite la testarea acestora. El poate să călătorească instant la aceste coordonate. Acestea fiind spuse, agentul nostru vă roagă să îl ajutaţi în misiunea sa.
Cerinţă
1. Aflaţi distanta minimă dintre punctul de infiltrare şi primul dispozitiv de teleportare. În caz că gaseşte un astfel de dispozitiv precizaţii distanţa minimă parcursă până la el, altfel afişaţi -1.
2. Aflaţi distanţa minimă pe care trebuie să o parcurgă agentul ca să ajungă în punctul de extragere al informaţiei.

Date de intrare

Fişierul de intrare agent.in conţine pe prima linie două numere întregi n şi m reprezentând dimensiunile metricei. Pe următoarele două linii se află câte două perechi de numere, ce reprezintă coordonatele de intrare si coordonatele punctului de extragere a informaţiei;
Pe a patra linie se află numărul k, reprezenând numărul de obstacole din matrice;
Pe următoarele k linii se află câte o pereche de numere, x si y, reprezentând coordonatele obstacolelor;
Pe a k+5 linie se află numărul de dipozitive de teleportare de pe hartă;
Pentru fiecare dispozitiv este precizat pe următoarea linie poziţia acestuia, numarul p, reprezentând numărul de coordonate salvate în el, iar pe următoarele p linii sunt precizate aceste coordonate.

Date de ieşire

Fişierul de ieşire agent.out va conţine:
-pe prima linie răspunsul la prima cerintă;
-pe a doua linie se cere afisat raspunsul la a doua cerinţă.

Restricţii

• 1<n,m<100;
• 1<=xi,xf<=n;
• 1<=yi,yf<=m;
• 1<=k<=n*m;
• 0<=p<=50;
• Există întotdeauna soluţie;
• Prima cerinţă reprezintă 30% din punctaj, în timp ce a doua cerinţă reprezintă restul de 70% din punctaj. Dacă alegeţi să rezolvaţi doar a doua cerinţa, este necesar să afişaţi şi o valoare pentru prima cerinţă, chiar dacă aceasta este greşită.

• Agentul poate să se deplaseze numai în diecţiile N, S, E, V;

Exemplu

Explicaţie

Cel mai apropiat dispozitiv faţă de punctul de intrare este cel cu indicele 1, aflat la distanţa de 2 unităţi. Agentul se teleportează în poziţia 1 8 din matrice cu dispozitivul 1, având mai departe 3 unitaţi până să ajungă la punctul de extragere al informaţiei.

Cum se trimit solutii?