vis

Vis

== include(page="template/taskheader" task_id="vis") ==

Ojilă este atât de obsedat de munca de pregătire pentru OJI, că rezolvă probleme şi în vis. El doarme şi visează că se află la poziţia (1,1) a unei matrice pătratice în care liniile şi coloanele sunt numerotate de la 1 la N. În matrice se află două poziţii speciale (L1, C1) şi (L2,C2). Ojilă poate să se deplaseze pe patru direcţii (nord, sud, est, vest) fără a părăsi matricea şi mergând numai pe valorile marcate cu 0. Dar dacă trece prin poziţia (L1,C1), atunci el poate mai departe să meargă şi pe poziţii care au valori mai mici sau egale cu un număr dat K1, iar dacă trece poziţia (L2,C2), atunci el poate mai departe să meargă şi pe poziţii care au valori mai mari sau egale cu un număr dat K2. Bineînţeles, dacă a trecut prin ambele poziţii speciale, atunci el poate merge pe toate valorile mai mici sau egale cu K1 ;i mai mari sau egale cu K2. Să se determine numărul minim de paşi necesar lui Ojilă pentru a ajunge ca prin vis în poziţia (N,N) din matrice.

Ojilă este atât de obsedat de munca de pregătire pentru OJI, că rezolvă probleme şi în vis. El doarme şi visează că se află la poziţia (1,1) a unei matrice pătratice în care liniile şi coloanele sunt numerotate de la 1 la N. În matrice se află două poziţii speciale (L1,C1) şi (L2,C2). Ojilă poate să se deplaseze pe patru direcţii (nord, sud, est, vest) fără a părăsi matricea şi mergând numai pe valorile marcate cu 0. Dar dacă trece prin poziţia (L1,C1), atunci el poate mai departe să meargă şi pe poziţii care au valori mai mici sau egale cu un număr dat K1, iar dacă trece prin poziţia (L2,C2), atunci el poate mai departe să meargă şi pe poziţii care au valori mai mari sau egale cu un număr dat K2. Bineînţeles, dacă a trecut prin ambele poziţii speciale, atunci el poate merge pe toate valorile mai mici sau egale cu K1 sau mai mari sau egale cu K2. Să se determine numărul minim de paşi necesar lui Ojilă pentru a ajunge ca prin vis în poziţia (N,N) din matrice.

h2. Restricţii

* $1 ≤ N ≤ 1000$

* $3 ≤ N ≤ 1000$

* Elementele vectorului sunt numere naturale mai mici sau egale cu 30 000.
* Poziţiile (1,1), (N,N), (L1, C1) şi (L2,C2) vor fi mereu marcate cu 0

* Se poate trece de oricate ori printr-o pozitie

* Pentru toate testele va exista un drum de la (1,1) la (N,N).
h2. Exemplu