== include(page="template/taskheader" task_id="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).
Poveste si cerinta...
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).
h2. Date de intrare
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).
Fisierul de intrare $poarta.in$ ...
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.
h2. Date de iesire
h2. Cerinta
In fisierul de iesire $poarta.out$ ...
Determinati timpul minim in care nava poate ajunge din zona initiala in cea finala, precum si numarul de trasee de durata minima.
h2. Restrictii
h2. 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 în care se afla porti stelare, cate o poarta pe o linie. Numerele de pe aceeasi linie sunt separate prin cate un spatiu.
h2. 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$.
h2. 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.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. poarta.in |_. poarta.out |
| 6 7 4
2 5 6 2
1 1
5 1
1 6
4 5
| 5
6
|
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="poarta") ==
