==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$}.

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

| 9 |
==Include(page="template/taskfooter" task_id="car")==

243