Fişierul intrare/ieşire:poarta.in, poarta.outSursăONI 2008, clasa a 10-a
AutorRadu VisinescuAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.05 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Poarta

Harta Galaxiei este reprezentata ca o matrice cu N linii (numerotate de la 1 la N) si M coloane (numerotate de la 1 la M). Orice element al matricei reprezinta o zona de forma patrata cu latura de 1 an lumina (denumita quadrant) si poate fi identificat prin coordonatele sale (numarul liniei si respectiv numarul coloanei pe care afla).

Nava Enterprise se afla intr-un quadrant de coordonate cunoscute si trebuie sa ajunga la destinatie (un alt quadrant, diferit de cel de plecare, de coordonate de asemenea cunoscute).

Nava se poate deplasa de la un quadrant la unul dintre cei invecinati pe orizontala sau verticala intr-o unitate de timp (mai exact, din zona de coordonate (L,C) nava se poate deplasa in una dintre zonele de coordonate (L-1,C), (L+1,C), (L,C-1), (L,C+1), fara a iesi de pe harta).

In plus, in unele zone (quadranti) se gasesc porti stelare. O poarta stelara permite deplasarea navei intr-o unitate de timp in oricare alta zona in care se gaseste o alta poarta stelara. Daca in drumul sau nava ajunge intr-o zona cu o poarta stelara, nava se poate deplasa intr-o alta zona cu poarta stelara sau poate sa-si continue drumul in una dintre zonele invecinate.

Cerinta

Determinati timpul minim in care nava poate ajunge din zona initiala in cea finala, precum si numarul de trasee de durata minima.

Datele de intrare

Fisierul de intrare poarta.in contine pe prima linie numerele naturale N M K, reprezentand in ordine, numarul de linii, numarul de coloane si respectiv numarul de porti stelare de pe harta. Pe cea de-a doua linie, se afla 4 numere naturale L1 C1 L2 C2, reprezentand coordonatele zonei de plecare, respectiv coordonatele zonei destinatie. Pe urmatoarele K linii sunt scrise coordonatele zonelor in care se afla porti stelare, cate o poarta pe o linie. Numerele de pe aceeasi linie sunt separate prin cate un spatiu.

Datele de iesire

Fisierul de iesire poarta.out va contine doua linii. Pe prima linie va fi scris numarul natural D, reprezentand timpul minim in care nava ajunge din zona initiala la destinatie. Pe cea de-a doua linie va fi scris numarul natural Nr, reprezentand numarul de trasee de durata minima. Deoarece numarul Nr poate fi foarte mare, trebuie sa afisati restul impartirii lui Nr la 997.

Restrictii si precizari

  • 1 ≤ N, M ≤ 100
  • 0 ≤ K ≤ 1000
  • Pentru 20% dintre teste 1 ≤ N, M ≤ 10, 0 ≤ K ≤ 10
  • Pentru determinarea corecta a timpului minim se acorda 30% din punctaj. Pentru determinarea corecta a timpului minim si a numarului de trasee de durata minima se acorda punctajul maxim.

Exemplu

poarta.inpoarta.out
6 7 4
2 5 6 2
1 1
5 1
1 6
4 5
5
6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content