Se consideră harta universului ca fiind o matrice cu 250 de linii şi 250 de coloane. În fiecare celulă se găseşte o aşa numită poartă stelară, iar în anumite celule se găsesc echipaje ale porţii stelare. La o deplasare, un echipaj se poate deplasa din locul în care se află în oricare alt loc în care se găseşte o a doua poartă, în cazul nostru în orice altă poziţie 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.

Cerinţă

Dându-se un număr p (1<p<5000) de echipaje, pentru fiecare echipaj fiind precizate poziţia iniţială şi poziţia finală, determinaţi numărul minim de deplasări necesare pentru ca toate echipajele să ajungă din poziţia iniţială în cea finală.

Date de intrare

Se citesc din fisierul text poartas.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 poziţiei iniţiale a unui echipaj (linie coloană), următoarele două reprezentând coordonatele poziţiei finale a aceluiaşi echipaj (linie coloană)

Date de ieşire

Pe prima linie a fişierului text poartas.out se scrie un singur număr reprezentând numărul minim de deplasări necesar.

Restricţii

Coordonatele poziţiilor iniţiale şi finale ale echipajelor sunt numere naturale din intervalul [1, 250].
Poziţiile iniţiale ale celor p echipaje sunt distincte două cîte două.
Poziţiile finale ale celor p echipaje sunt distincte două câte două.

Exemple

poartas.in	poartas.out	Explicaţii
3 1 2 3 4 6 5 3 9 3 4 1 2	4

autor: Prof. Radu Vişinescu

propunător: Prof. Marinel Şerban

Liceul de Informatica

marinel.serban@gmail.com