== include(page="template/taskheader" task_id="exit") ==
Poveste si cerinta...
Doi prieteni (Ionel si Gigel) au ramas blocati in interiorul unui labirint alcatuit din $X x Y$ celule (coordonatele celulelor iau valori de la $0$ la $X-1$, respectiv de la $0$ la $Y-1$). Dintre aceste celule, numai in $C$ celule se poate intra, celelalte fiind blocate. Dintr-o celula $(x,y)$ se pot efectua deplasari numai catre una din cele $4$ celule invecinate: catre nord, in celula $(x,y+1)$; catre est, in celula $(x+1,y)$; catre sud, in celula $(x,y-1)$; catre vest, in celula $(x-1,y)$. Deplasarea se poate realiza numai daca nu se iese din labirint si daca pasajul de trecere catre celula invecinata nu este blocat. Costul unei astfel de deplasari este $1$ unitate.
Cei doi prieteni cunosc coordonatele a $N$ celule *magice* pe care trebuie sa le *viziteze* in ordine. Celulele magice trebuie *vizitate* de cel putin unul dintre cei doi prieteni, insa nu neaparat de catre amandoi. Initial, Ionel si Gigel se afla in celula $(x{~0~},y{~0~})$. De aici, unul dintre ei (sau amandoi) se va (vor) duce in prima celula magica. Dupa ce Ionel sau Gigel (sau amandoi) a (au) ajuns in a $i$-a celula magica, unul dintre ei (sau amandoi) se va (vor) deplasa in a $(i+1)$-a celula magica. Intre doua celule magice (sau intre celula initiala si prima celula magica) se poate trece si prin alte celule magice, insa a $i$-a celula magica se considera *vizitata* atunci cand unul din cei doi prieteni ajunge in ea doar daca: $i=1$ sau a fost deja *vizitata* a $(i-1)$-a celula magica.
Dupa vizitarea celei de-a $N$-a celule magice, ambii prieteni trebuie sa ajunga in aceasta celula, pentru a putea parasi, in sfarsit, labirintul.
Determinati costul total minim al deplasarilor efectuate de cei doi prieteni pentru a vizita cele $N$ celule magice si a ajunge amandoi in a $N$-a celula magica.
h2. Date de intrare
Fisierul de intrare $exit.in$ ...
Prima linie a fisierului de intrare $exit.in$ contine $6$ numere intregi, separate prin cate un spatiu: $N, X, Y, x{~0~}, y{~0~}, C$. Urmatoarele $C$ linii contin cate $6$ numere intregi, separate prin cate un spatiu: $xc, yc, nord, est, sud, vest$. $(xc,yc)$ reprezinta coordonatele unei celule, iar $nord, est, sud$ si $vest$ sunt numere din multimea ${0,1}$. Daca numarul este $1$, atunci pasajul catre celula invecinata din directia respectiva este blocat (iar daca este $0$, pasajul este liber). Pasajele blocate vor fi simetrice (daca o celula are pasajul blocat catre nord, atunci si celula dinspre nord, daca nu este o celula blocata, va avea pasajul blocat in directia sud). Urmatoarele $N$ linii contin cate doua numere intregi, separate printr-un spatiu. A $i$-a dintre aceste linii contine numerele $xm{~i~}, ym{~i~}$, reprezentand coordonatele celei de-a $i$-a celule magice.
h2. Date de iesire
In fisierul de iesire $exit.out$ ...
In fisierul de iesire $exit.out$ veti afisa costul total minim al deplasarilor efectuate de cei doi prieteni pana ce acestia ajung in ultima celula magica.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ X, Y ≤ 100$
* $1 ≤ C ≤ X * Y$
* $1 ≤ N ≤ 1000$
* Se garanteaza ca cei doi prieteni vor putea vizita cele $N$ celule magice.
h2. Exemplu
table(example). |_. exit.in |_. exit.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
...
|2 3 2 0 1 6
0 0 1 1 1 1
0 1 1 0 1 1
1 0 1 0 1 1
1 1 1 0 1 0
2 0 0 1 1 0
2 1 1 1 0 0
2 1
0 1
|4|
== include(page="template/taskfooter" task_id="exit") ==
