== include(page="template/taskheader" task_id="vis") ==
Poveste şi cerinţă...
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. Date de intrare
Fişierul de intrare $vis.in$ ...
Fişierul de intrare $vis.in$ conţine pe prima linie numerele naturale N, K1, K2, L1, C1, L2, C2 separate prin câte un spaţiu. Pe următoarele N linii se află câte N numere naturale separate prin câte un spaţiu reprezentând câte o linie a matricei.
h2. Date de ieşire
În fişierul de ieşire $vis.out$ ...
Fişierul de ieşire $vis.out$ va conţine un singur număr natural reprezentând lungimea minimă a drumului de la poziţia (1,1) la (N,N).
h2. Restricţii
* $... ≤ ... ≤ ...$
* $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
table(example). |_. vis.in |_. vis.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 2 5 3 1 1 5
0 3 0 0 0
0 0 7 0 0
0 5 2 0 0
1 6 0 9 0
0 0 0 8 0
| 13
|
h3. Explicaţie
...
K1=2, K2=5, (L1, C1)=(3,1) şi (L2,C2)=(1,5). Drumul de lungime 13 este (1,1) (2,1) (3,1) (4,1) (5,1) (5,2) (5,3) (4,3) (3,3) (3,4) (3,5) (4,5)(5,5)
== include(page="template/taskfooter" task_id="vis") ==
