exit

Exit

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 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.

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.

h2. Restrictii
* $1 ≤ X, Y ≤ 100$

* $1 ≤ c ≤ X * Y$

* $1 ≤ C ≤ X * Y$

* $1 ≤ N ≤ 1000$
* Se garanteaza ca cei doi prieteni vor putea vizita cele $N$ celule magice.

|4|
== include(page="template/taskfooter" task_id="exit") ==

3242