parc

In fiecare zi Gigel vine de la scoala acasa trecand prin parc. Parcul este un teren de forma patrata care are un obstacol (o groapa) pe care Gigel trebuie sa o ocoleasca. Dupa multe drumuri Gigel nu a reusit inca sa-si dea seama care e cel mai scurt drum spre casa; trebuie sa ocoleasca groapa prin stanga sau prin dreapta? Pentru a-l ajuta sa afle raspunsul la intrebare Gigel va pune la dispozitie o harta a parcului sub forma unei matrice patrata cu valori 0 si 1, 0 reprezentand terenul accesibil, 1 obstacolul. Scoala este in coltul stanga-sus al matricei iar casa in coltul din dreapta jos. Cele 4 margini ale terenului sunt accesibile. Pentru a trece dintr-o celula a matricei intr-o celula invecinata pe orizontala, verticala sau diagonala Gigel face un pas. El nu face salturi, deci nu poate trece dintr-o celula decat intr-una din cele maximum 8 celule invecinate.

Pe prima linie a fisierului de intrare parc.in se gaseste dimensiunea matricei. Pe urmatoarele linii e descrisa matricea ca un sir de 0 sau 1 cu cate un spatiu intre numerele de pe aceeasi linie.

Prima linie a fisierului parc.out va contine doua numere separate de un spatiu. Primul numar reprezinta numarul minim de pasi prin care se poate ajunge de la scoala acasa mergand prin stanga obstacolului, al doilea numar - numarul minim de pasi necesari mergand prin dreapta obstacolului. Stanga si dreapta se considera in raport cu directia de mers.

• 3 £ dimensiunea matricei £ 250

parc.in	parc.out
5 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0	5 8

Timp maxim de executie/test: 0.1 secunde