2140 - Poartas

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

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

poartas.out

4

def citire_date(nume_fisier):
    import sys
    input = sys.stdin.read
    data = input().strip().split()
    
    # Parcurgem datele
    index = 0
    p = int(data[index])
    index += 1
    echipaje = []
    for _ in range(p):
        x1, y1, x2, y2 = map(int, data[index:index+4])
        echipaje.append(((x1, y1), (x2, y2)))
        index += 4
    
    return p, echipaje

def floyd_warshall(dist, noduri):
    # Aplicam algoritmul lui Floyd-Warshall pentru toate perechile de noduri
    for k in range(noduri):
        for i in range(noduri):
            for j in range(noduri):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

def numar_minim_deplasari(p, echipaje):
    # Initializare matrice de distante mari (infinite)
    INF = float('inf')
    # Creem un dictionar pentru a stoca distantele intre porțile stelare
    noduri = {}
    index_nod = 0
    for ((x1, y1), (x2, y2)) in echipaje:
        if (x1, y1) not in noduri:
            noduri[(x1, y1)] = index_nod
            index_nod += 1
        if (x2, y2) not in noduri:
            noduri[(x2, y2)] = index_nod
            index_nod += 1

    num_noduri = len(noduri)
    dist = [[INF] * num_noduri for _ in range(num_noduri)]

    # Setam distanta de la un nod la sine insusi la 0
    for i in range(num_noduri):
        dist[i][i] = 0

    # Setam distantele initiale (doar distanta directa dintre noduri)
    for ((x1, y1), (x2, y2)) in echipaje:
        nod1 = noduri[(x1, y1)]
        nod2 = noduri[(x2, y2)]
        dist[nod1][nod2] = 1
        dist[nod2][nod1] = 1
    
    floyd_warshall(dist, num_noduri)

    total_deplasari = 0
    for ((x1, y1), (x2, y2)) in echipaje:
        nod1 = noduri[(x1, y1)]
        nod2 = noduri[(x2, y2)]
        total_deplasari += dist[nod1][nod2]
    
    return total_deplasari

def scrie_rezultate(nume_fisier, total_deplasari):
    with open(nume_fisier, 'w') as f:
        f.write(f"{total_deplasari}\n")

# Main function
def main():
    p, echipaje = citire_date('date.in')
    total_deplasari = numar_minim_deplasari(p, echipaje)
    scrie_rezultate('date.out', total_deplasari)

if __name__ == '__main__':
    main()