Doi hoți au reușit să intre în Marea Piramidă a lui Keops. Nici unul dintre ei nu știe de prezența celuilalt.
Piramida poate fi privită ca un caroiaj cu m linii și n coloane. Se cunosc coordonatele la care se află inițial hoții. În fiecare minut un hoț se poate deplasa din poziția sa într-o poziție vecină pe verticală sau pe orizontală dacă aceasta este accesibilă. Va trebui să determinați numărul minim de minute necesare pentru ca cei doi hoți să se întâlnească.
Prima linie a fișierului de intrare KEOPS.IN conține valorile m și n care reprezintă dimensiunile piramidei. Cea de-a doua linie conține coordonatele l1 și c1 (linia și coloana) ale primului hoț, iar cea de-a treia linie conține coordonatele l2 și c2 (linia și coloana) ale celui de-al doilea hoț. Numerele de pe aceste linii sunt separate prin spații. Pe fiecare dintre următoarele m linii se află un șir de n numere neseparate prin spații. Valorile acestor numere pot fi 0 sau 1. Valoarea 0 indică faptul că celula corespunzătoare este accesibilă, iar valoarea 1 indică faptul că celula este inaccesibilă.
Fișierul de ieșire KEOPS.OUT trebuie să conțină o singură linie pe care se va afla numărul minim de minute necesare pentru ca cei doi hoți să se întâlnească. Dacă nu există posibilitatea ca cei doi hoți să se întâlnească, valoarea scrisă va fi -1.
KEOPS.IN
5 5 5 5 1 1 00000 11110 00000 01111 00000 KEOPS.OUT 8
|