| Fişierul intrare/ieşire: | exit.in, exit.out | Sursă | Selectie echipe ACM ICPC, UPB 2008 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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 (x0,y0). 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.
Date de intrare
Prima linie a fisierului de intrare exit.in contine 6 numere intregi, separate prin cate un spatiu: N, X, Y, x0, y0, 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 xmi, ymi, reprezentand coordonatele celei de-a i-a celule magice.
Date de iesire
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.
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.
Exemplu
| exit.in | exit.out |
|---|---|
| 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 |
