Fişierul intrare/ieşire: | car.in, car.out | Sursă | preONI 2005 Runda 2 |
Autor | Cosmin Silvestru Negruseri | Adăugată de | |
Timp execuţie pe test | 0.15 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
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.
Cerinta
Determinati pentru Ionel costul minim din punct de vedere al curbelor de la o pozitie initiala la o pozitie finala.
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.
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.
Restrictii
- 0 ≤ N, M ≤ 500
Exemplu
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 |