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ța

Dându-se un număr p 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 poartas.in conține pe prima linie numărul p reprezentând numărul echipaje, iar 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

Fișierul de ieșire poartas.out va conține un singur număr reprezentând numărul minim de deplasări necesar.

Restricții și precizări

coordonatele pozițiilor inițiale și finale ale echipajelor sunt numere naturale din intervalul [1, 250]
1<p<5000
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

poartas.in

poartas.out

Explicații

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema poartas:

#include <fstream>

using namespace std;

struct pereche
{
    short x, y;
};

pereche a[251][251];

int NrPasi(short p, short q, short cnt)
{
    if (a[p][q].x == p && a[p][q].y == q) return 0;
    short i, j;
    int nrp = 0;
    i = p; j = q;
    while (true)
    {
        nrp++;
        p = a[i][j].x;
        q = a[i][j].y;
        a[i][j].x = a[i][j].y = cnt;
        i = p; j = q;
        if (a[i][j].x == 0) return nrp;
        if (a[i][j].x == cnt) return nrp + 1;
        if (a[i][j].x < 0) return nrp;
    }
    return 1;
}

int main()
{
    int nrTotal;
    short xs, ys, i, j, P, cnt;
    pereche w;

    /// citire
    ifstream fin("poartas.in");
    fin >> P;
    for (i = 1; i <= P; i++)
    {
        fin >> xs >> ys >> w.x >> w.y;
        a[xs][ys] = w;
    }
    fin.close();

    /// calcul
    nrTotal = cnt = 0;
    for (i = 1; i <= 250; i++)
        for (j = 1; j <= 250; j++)
            if (a[i][j].x > 0)
            {
                cnt--;
                nrTotal += NrPasi(i, j, cnt);
            }

    /// afisare
    ofstream fout("poartas.out");
    fout << nrTotal << "\n";
    fout.close();

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2140 poartas

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2140 poartas de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2140 poartas