Fişierul intrare/ieşire:vis.in, vis.outSursăpreOJI 2016, clasa a 10-a
AutorGemene Narcis - GabrielAdăugată denarcis_vsGemene Narcis - Gabriel narcis_vs
Timp execuţie pe test0.7 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.invis.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)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?