Editing 2140 - Poartas

Se consideră harta universului ca fiind o matrice cu <code>250</code> de linii și <code>250</code> 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 <code>p</code> 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 <code>poartas.in</code> conține pe prima linie numărul <code>p</code> reprezentând numărul  echipaje, iar pe următoarele <code>p</code> linii câte <code>4</code> 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 <code>poartas.out</code> 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 <code>[1, 250]</code>
* <code>1 < p < 5000</code>
* pozițiile inițiale ale celor <code>p</code> echipaje sunt distincte două câte două
* pozițiile finale ale celor <code>p</code> echipaje sunt distincte două câte două

= Exemplu: =
<code>poartas.in</code>
 3
 1 2 3 4
 6 5 3 9
 3 4 1 2
<code>poartas.out</code>
 4
<syntaxhighlight lang="python" line="1">
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()
</syntaxhighlight>