== include(page="template/taskheader" task_id="poarta") ==
Poveste si cerinta...
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).
h2. Date de intrare
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).
Fisierul de intrare $poarta.in$ ...
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).
h2. Date de iesire
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.
In fisierul de iesire $poarta.out$ ...
h2. Cerinta
h2. Restrictii
Determinati timpul minim in care nava poate ajunge din zona initiala in cea finala, precum si numarul de trasee de durata minima.
* $... ≤ ... ≤ ...$
h2. Datele de intrare
h2. Exemplu
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.
table(example). |_. poarta.in |_. poarta.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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
h3. Explicatie
* $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
|
== include(page="template/taskfooter" task_id="poarta") ==
