Fișierul intrare/ieșire poarta.in, poarta.out Sursă OJI 2002 clasa a 9-a
Autor Radu Vișinescu Adăugată de avatar vladcainamisir Vlad Cainamisir vladcainamisir
Timp de execuție pe test 1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Poarta ( clasa a 9-a )

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.

Cerinta

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

Fișierul de intrare poarta.in
Se citesc din fisierul text poarta.in în următorul format:
– pe prima linie numărul natural p reprezentând numărul de 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

În fișierul de ieșire poarta.out
Pe prima linie a fișierului text poarta.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ă.

Exemplu

poarta.in poarta.out
3
1 2 3 4
6 5 3 9
3 4 1 2
4

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii