Editing 3949 - mindist

==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 '''mindistin.txt''' 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 '''mindistout.txt''' 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'''

==Exemplul 1:==

'''mindistin.txt'''

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

'''mindistout.txt'''

 Datele de intrare corespund restrictiilor impuse
 0 1 1 2 
 -1 1 0 1 
 2 1 0 -1 
 -1 -1 -1 -1 

==Exemplul 2:==

'''mindistin.txt'''

 51

'''mindistout.txt'''

 Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

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

from collections import deque


def validare(numar_n, numar_m, numar_k):  # functia de validare a datelor de intrare
    if numar_n < 1 or numar_n > 1000 or numar_m < 1 or numar_m > numar_n*numar_n or numar_k < 1 or numar_k > n*n:
        raise ValueError
    file_out.write("Datele de intrare corespund restrictiilor impuse\n")


def mindist(numar_n, blocked, proteins):  # functia de rezolvare
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    matrix = [[-1 for _ in range(numar_n)] for _ in range(numar_n)]
    queue = deque()
    for b in blocked:
        matrix[b[0]-1][b[1]-1] = -2
    for p in proteins:
        queue.append((p[0]-1, p[1]-1))
        matrix[p[0]-1][p[1]-1] = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < numar_n and 0 <= ny < numar_n and matrix[nx][ny] == -1:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append((nx, ny))
    return matrix


if __name__ == '__main__':
    try:
        file_in = open("mindistin.txt", "r")         # declararea fisierelor
        file_out = open("mindistout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)
        n, m, k = map(int, file_in.readline().split())
        blocat = [tuple(map(int, file_in.readline().split())) for _ in range(m)]
        proteine = [tuple(map(int, file_in.readline().split())) for _ in range(k)]
        validare(n, m, k)
        result = mindist(n, blocat, proteine)
        for row in result:
            file_out.write(' '.join(str(x) if x != -2 else '-1' for x in row))
            file_out.write('\n')
    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")

</syntaxhighlight>