Olimpiada Jude
teană de InformaticăCLASA a IX-a
PROBLEMA 1 (Poarta)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 m
ai 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ă.Datele de intrare
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ă).
Datele de iesire
Pe prima linie a fisierului text poarta.out se scrie un singur număr reprezentând numărul minim de deplasări necesar.
Exemplu:
poarta.in3
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