Bonte Lucas Gabriel at 19:54, 15 November 2023

2023-11-15T19:54:30Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== MăcGregăr se află într-o matrice pătratică cu '''N''' linii și '''N''' coloane. Aflându-se în celula '''(i, j)''' acesta se poate deplasa printr-un pas într-una din celulele '''(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)'''. Sunt '''M''' celule distincte prin care el nu poate trece, deoarece sunt ocupate cu echipamentul lui sportiv. De asemenea, mai sunt '''K''' celule distincte, diferite de cele ocupate, în care se află proteina lui MăcGregăr....

2023-11-06T17:59:07Z

Pagină nouă: ==Cerința== MăcGregăr se află într-o matrice pătratică cu '''N''' linii și '''N''' coloane. Aflându-se în celula '''(i, j)''' acesta se poate deplasa printr-un pas într-una din celulele '''(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)'''. Sunt '''M''' celule distincte prin care el nu poate trece, deoarece sunt ocupate cu echipamentul lui sportiv. De asemenea, mai sunt '''K''' celule distincte, diferite de cele ocupate, în care se află proteina lui MăcGregăr....

New page

==Cerința==

MăcGregăr se află într-o matrice pătratică cu '''N''' linii și '''N''' coloane. Aflându-se în celula '''(i, j)''' acesta se poate deplasa printr-un pas într-una din celulele '''(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)'''. Sunt '''M''' celule distincte prin care el nu poate trece, deoarece sunt ocupate cu echipamentul lui sportiv. De asemenea, mai sunt '''K''' celule distincte, diferite de cele ocupate, în care se află proteina lui MăcGregăr. Pentru fiecare celulă din matrice din care acesta ar pleca, MăcGregăr se întreabă care este numărul minim de pași pentru a ajunge la cea mai apropiată proteină.

==Date de intrare==

Fișierul de intrare '''mindist.in''' conține pe prima linie numerele '''N''', '''M''' și '''K''' separate printr-un spațiu. Pe următoarele '''M''' linii se află câte două numere naturale reprezentând linia și coloana pe care se află o celulă ocupată. Pe următoarele '''K''' linii se află câte două numere naturale reprezentând linia și coloana pe care se află o proteină.

==Date de ieșire==

Fișierul de ieșire '''mindist.out''' va conține '''N''' linii, fiecare linie va conține '''N''' numere întregi, separate printr-un spațiu. Pe linia '''i''', a '''j'''-a valoare reprezintă numărul minim de pași pentru a ajunge din celula '''(i, j)''' la cea mai apropiată proteină, dacă un astfel de drum există, '''-1''' altfel.

==Restricții și precizări==

*'''1 ≤ M ≤ N * N'''
*'''1 ≤ K ≤ N * N'''
*Pentru 30p, avem '''1 ≤ N ≤ 50'''
*Pentru alte 30p, avem '''1 ≤ N ≤ 1000''' și '''1 ≤ K ≤ 10'''
*Pentru restul de 40p, avem '''1 ≤ N ≤ 1000'''

==Exemplu:==

'''mindist.in'''

:4 5 3
:4 3
:2 1
:4 2
:4 1
:3 4
:3 3
:2 3
:1 1

'''mindist.out'''

:0 1 1 2
:-1 1 0 1
:2 1 0 -1
:-1 -1 -1 -1

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque

def mindist(N, M, K, blocked, proteins):
# Definim directiile in care se poate deplasa MacGregor
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# Initializam matricea cu -1
matrix = [[-1 for _ in range(N)] for _ in range(N)]

# Initializam coada pentru BFS
queue = deque()

# Marcam celulele blocate cu -2
for b in blocked:
matrix[b[0]-1][b[1]-1] = -2

# Adaugam proteinele in coada si le marcam cu 0 in matrice
for p in proteins:
queue.append((p[0]-1, p[1]-1))
matrix[p[0]-1][p[1]-1] = 0

# Parcurgem coada
while queue:
x, y = queue.popleft()
# Incercam sa ne deplasam in toate directiile
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# Verificam daca noua pozitie este valida si nevizitata
if nx >= 0 and nx < N and ny >= 0 and ny < N and matrix[nx][ny] == -1:
# Actualizam distanta si adaugam pozitia in coada
matrix[nx][ny] = matrix[x][y] + 1
queue.append((nx, ny))

return matrix

# Datele de intrare
N = 4
M = 5
K = 3
blocked = [(4, 3), (2, 1), (4, 2), (4, 1), (3, 4)]
proteins = [(3, 3), (2, 3), (1, 1)]

# Apelam functia
result = mindist(N, M, K, blocked, proteins)

# Scriem rezultatul in fisier
with open('mindist.out', 'w') as f:
for row in result:
f.write(' '.join(str(x) if x != -2 else '-1' for x in row))
f.write('\n')

</syntaxhighlight>

3949 - mindist - Revision history

Bonte Lucas Gabriel at 19:54, 15 November 2023