| Fişierul intrare/ieşire: | vis.in, vis.out | Sursă | preOJI 2016, clasa a 10-a |
| Autor | Gemene Narcis - Gabriel | Adăugată de |  Gemene Narcis - Gabriel •narcis_vs |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
Vezi solutiile trimise | Statistici
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 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.
Date de intrare
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.
Date de ieşire
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).
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).
Exemplu
| vis.in | vis.out |
|---|---|
| 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 |
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)
