==Include(page="template/taskheader" task_id="car")==
 
==Include(page="template/raw")==
 
Link: [1]File-List
 
car
 
 
 
Ionel a implinit 18 ani si a luat permisul de conducere, azi vrea sa mearga de la el acasa pana la scoala cu masina si singura conditie pe care i-a impus-o tatal sau e aceea de a nu lua foarte multe curbe! Pentru a primi masina si alta data, Ionel vrea sa il impresioneze pe tatal sau si sa mearga pe drumul cel mai putin costisitor din punct de vedere al curbelor. Orasul e reprezentat de o matrice de N linii si M coloane, un element al matricii fiind 0 daca pe acolo poate trece masina si 1 daca nu. Masina se poate misca dintr-o celula a matricii in toate cele 8 celule adiacente, daca ele sunt libere. Costul unui drum de la pozitia initiala la pozitia finala este data de suma costurilor miscarilor. O miscare in directia de mers are costul 0, o miscare la 45 de grade fata de directia de mers are costul 1, o miscare la 90 de grade are costul 2, una la 135 de grade are costul 3 iar una la 180 de grade are costul 4. La momentul initial masina poate porni in oricare dintre cele 8 directii, daca celula din
directia respectiva este marcata cu 0.
 
h2. Cerinta
 
Determinati pentru Ionel costul minim din punct de vedere al curbelor de la o pozitie initiala la o pozitie finala.
 
h2. Date de Intrare (fisier: car.in)
 
Pe prima linie se gasesec doua numere naturale: N (numarul de linii al matricii) si M (numarul de coloane al matricii). Pe urmatoarea linie sunt numerele Si - linia pozitiei initiale a masinii lui Ionel, Sj - coloana pozitiei initiale ale masinii lui Ionel, Fi - linia pozitiei finale, Fj - coloana pozitiei finale. Pe urmatoarele N linii sunt cate M numere de 0 sau 1.
 
h2. Date de Iesire (fisier: car.out)
 
Pe prima linie se va gasi costul minim al unui drum de la pozitia initiala la pozitia finala. Daca nu exista nici un drum se va afisa -1.
 
h2. Restrictii
 
S 0 <= N, M <= 500
 
h2. Exemplu
 
car.in car.out
5 5 9
 
1 1 1 4
 
0 1 1 0 1
 
1 0 1 0 1
 
0 1 1 1 0
 
1 0 1 0 1
 
1 1 0 1 1
 

==Include(page="template/taskheader" task_id="car")==
 
Ionel a implinit 18 ani si a luat permisul de conducere, azi vrea sa mearga de la el acasa pana la scoala cu masina si singura conditie pe care i-a impus-o tatal sau e aceea de a nu lua foarte multe curbe! Pentru a primi masina si alta data, Ionel vrea sa il impresioneze pe tatal sau si sa mearga pe drumul cel mai putin costisitor din punct de vedere al curbelor. Orasul e reprezentat de o matrice de $N$ linii si $M$ coloane, un element al matricii fiind $0$ daca pe acolo poate trece masina si $1$ daca nu. Masina se poate misca dintr-o celula a matricii in toate cele $8$ celule adiacente, daca ele sunt libere. Costul unui drum de la pozitia initiala la pozitia finala este data de suma costurilor miscarilor. O miscare in directia de mers are costul {$0$}, o miscare la $45$ de grade fata de directia de mers are costul {$1$}, o miscare la $90$ de grade are costul {$2$}, una la $135$ de grade are costul $3$ iar una la $180$ de grade are costul {$4$}. La momentul initial masina poate porni in oricare dintre cele $8$ directii, daca celula din directia respectiva este marcata cu {$0$}.
 
h2. Cerinta
 
Determinati pentru Ionel costul minim din punct de vedere al curbelor de la o pozitie initiala la o pozitie finala.
 
h2. Date de Intrare
 
Pe prima linie a fisierului de intrare $car.in$ se gasesec doua numere naturale: $N$ (numarul de linii al matricii) si $M$ (numarul de coloane al matricii). Pe urmatoarea linie sunt numerele $Si$ - linia pozitiei initiale a masinii lui Ionel, $Sj$ - coloana pozitiei initiale ale masinii lui Ionel, $Fi$ - linia pozitiei finale, $Fj$ - coloana pozitiei finale. Pe urmatoarele $N$ linii sunt cate $M$ numere de $0$ sau {$1$}.
 
h2. Date de Iesire
 
Pe prima linie a fisierului de iesire $car.out$ se va gasi costul minim al unui drum de la pozitia initiala la pozitia finala. Daca nu exista nici un drum se va afisa {$-1$}.
 
h2. Restrictii
 
* $0 ≤ N, M ≤ 500$
 
h2. Exemplu
 
table(example). |_. car.in |_. car.out |
| 5 5
1 1 1 4
0 1 1 0 1
1 0 1 0 1
0 1 1 1 0
1 0 1 0 1
1 1 0 1 1
| 9 |
 
==Include(page="template/taskfooter" task_id="car")==

References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/car/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="car")==

243