RaulOtet: Pagină nouă: 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...

2024-07-26T08:14:12Z

Pagină nouă: 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...

New page

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>

2140 - Poartas - Revision history