Ana şi Bogdan au inventat un nou model de şotron. Ei desenează cu creta pe asfalt un caroiaj format din NxM pătrate organizate în N linii şi M coloane. O parte dintre aceste pătrate le colorează în roşu, celelalte în verde. În plus, un pătrat este selectat că pătrat de start şi un alt pătrat ca pătrat de final (acestea sunt verzi).
Scopul jocului este ca jucătorul să ajungă de la pătratul de start la pătratul final în cel mai scurt timp. Regulile jocului sunt:
este interzis ca jucătorul să păşească într-un pătrat roşu; este permis să se deplaseze doar în cele verzi;
atunci când jucătorul ajunge într-un pătrat el se poate deplasa în pătratul din faţa sa, în cel din stânga sa sau în cel din dreapta sa (faţa, stânga, dreapta sunt stabilite evident în funcţie de sensul de mers); prin urmare este interzis ca un jucător să se deplaseze înapoi sau în diagonală; de asemenea este interzis ca jucătorul să părăsească caroiajul;
de-a lungul întregului drum de la start la final sunt permise în total cel mult K deplasări la dreapta;
iniţial, când jucătorul este plasat în pătratul de start, el poate alege ce sens de deplasare doreşte;
deplasarea de la un pătrat la altul durează o secundă.
Cerinţă
Scrieţi un program care să determine timpul minim necesar jucătorului pentru a ajunge din pătratul de start în pătratul final, respectând regulile din enunţ (dacă este posibil).
Date de intrare
Fişierul de intrare sotron1.in conţine pe prima linie trei numere naturale K N M, reprezentând numărul maxim de deplasări la dreapta, numărul de linii şi respectiv numărul de coloane ale şotronului.
Pe următoarele N linii se află câte M numere din mulţimea {0, 1, 2, 3} cu următoarea semnificaţie: 0 reprezintă un pătrat verde 1 reprezintă un pătrat roşu 2 reprezintă pătratul de start (există un singur element 2) 3 reprezintă pătratul final (există un singur element 3).
Date de ieşire
Fişierul de ieşire sotron1.out va conţine o singură linie pe care va fi scris timpul minim necesar pentru a ajunge din pătratul de start în pătratul final, respectând regulile din enunţ. Dacă problema nu are soluţie, pe prima linie se va afişa valoarea -1.