Document Microsoft Word

Se consideră harta universului ca fiind o matrice cu 250 de linii si 250 de coloane. În fiecare celulă se găseste o asa numită poartă stelară, iar în anumite celule se găsesc echipaje ale portii stelare. La o deplasare, un echipaj se poate deplasa din locul în care se află în oricare alt loc în care se găseste o a doua poartă, în cazul nostru în orice altă pozitie din matrice. Nu se permite situarea simultană a mai mult de un echipaj într-o celulă. La un moment dat un singur echipaj se poate deplasa de la o poartă stelară la alta.

Dându-se un număr p (1<p<5000) de echipaje, pentru fiecare echipaj fiind precizate pozitia initială si pozitia finală, determinati numărul minim de deplasări necesare pentru ca toate echipajele să ajungă din pozitia initială în cea finală.

Se citesc din fisierul text poarta.in în următorul format:

– pe prima linie numărul natural p reprezentând numărul echipaje,

– pe următoarele p linii câte 4 numere naturale, primele două reprezentând coordonatele pozitiei initiale a unui echipaj (linie coloană), următoarele două reprezentând coordonatele pozitiei finale a aceluiasi echipaj (linie coloană).

Pe prima linie a fisierului text poarta.out se scrie un singur număr reprezentând numărul minim de deplasări necesar.

3
1 2 3 4
6 5 3 9
3 4 1 2

poarta.out
4

Observatii:

– coordonatele pozitiilor initiale si finale ale echipajelor sunt numere naturale din intervalul [1, 250]
– pozitiile initiale ale celor p echipaje sunt distincte două cîte două;
– pozitiile finale ale celor p echipaje sunt distincte două câte două.

Timp maxim de executare: 1 sec/test

Pentru revenire inchideti fereastra curenta