Editing 4052 - emigrare

==Cerința==

Tărâmul emigranților se poate reprezenta printr-o matrice de dimensiuni '''n×m'''. O țară este formată din toate celulele care au o anumită valoare. În fiecare celulă locuiește un om. Pe tărâmul emigranților fiecare om este nemulțumit și vrea să ajungă în orice altă țară în cel mai scurt timp posibil.

Calculați pentru fiecare celulă distanța minimă până la o celulă de valoare diferită.

==Date de intrare==

Pe prima linie se află numerele '''n''' și '''m'''. Pe a '''i'''-a dintre următoarele '''n''' linii se găsește o secvență de '''m''' numere. Al '''j'''-lea număr se notează '''ai,j''' și reprezintă țara din care face parte celula '''(i,j)'''
.

==Date de ieșire==

Se vor afișa '''nm''' numere naturale reprezenând distanțele pentru fiecare om în parte. Pe a '''i'''-a dintre cele '''n''' linii se găsește o secvență de '''m''' numere. Al '''j'''-lea număr se notează '''di,j''' și reprezintă distanța minimă ce trebuie să o parcurgă omul din celula '''(i,j)''' pentru a ajunge în altă țară.

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

*'''2≤n,m≤10^3'''
*Se garantează că există cel puțin două țări
*Celulele unei țări nu sunt neapărat conectate
*Pentru '''20''' de puncte, '''n,m≤10'''
*Pentru '''40''' de puncte, '''n,m≤40'''

==Exemplul 1:==

;Intrare

 8 9 
 1 1 1 1 1 1 1 1 1
 1 1 4 4 1 3 3 3 3
 1 4 4 4 3 3 3 3 3
 1 4 4 4 3 3 3 3 3
 1 2 1 1 3 3 3 3 3
 2 2 2 1 1 3 3 3 3
 4 2 2 2 2 2 2 3 3
 4 4 2 2 2 2 2 3 3

;Ieșire

 Datele de intrare corespund restrictiilor impuse.
 2 1 0 0 1 0 0 0 0
 1 0 0 0 0 0 0 0 0
 0 0 1 0 0 1 1 1 1
 0 0 0 0 0 1 2 2 2
 0 0 0 0 0 1 1 2 3
 0 1 0 0 0 0 0 1 2
 0 0 1 0 0 0 0 0 1
 1 0 0 1 1 1 0 0 1

==Exemplul 2:==

;Intrare

 emigrare

;Ieșire

 Datele de intrare nu corespund restrictiilor impuse.

==Explicație==

Cele '''4''' țări sunt reprezentate de valorile '''1, 2, 3, 4.'''

==Rezolvare==

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

from collections import deque


def verificare_restrictii(nr_n, nr_m):    # functia de verificare a datelor de intrare
    if 2 <= nr_n <= 10**3 and 2 <= nr_m <= 10**3:
        return True
    else:
        return False


def min_distance(nr_n, nr_m, matrice):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    visited = [[False] * nr_m for _ in range(nr_n)]
    distanta = [[0] * nr_m for _ in range(nr_n)]

    q = deque()

    for i in range(nr_n):
        for j in range(nr_m):
            if any(matrice[i][j] != matrice[i + dx[k]][j + dy[k]] for k in range(4) if 0 <= i + dx[k] < nr_n and 0 <= j + dy[k] < nr_m):
                q.append((i, j))
                visited[i][j] = True

    while q:
        x, y = q.popleft()
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < nr_n and 0 <= ny < nr_m and not visited[nx][ny]:
                distanta[nx][ny] = distanta[x][y] + 1
                q.append((nx, ny))
                visited[nx][ny] = True

    return distanta

# Rularea se face in felul urmator, se scrie de la tastatura 8, apoi 9, apoi toata matricea


if __name__ == '__main__':
    try:
        n = int(input("Introduceti numarul de linii: "))
        m = int(input("Introduceti numarul de coloane: "))

        if verificare_restrictii(n, m):
            print("Datele de intrare corespund restrictiilor impuse.")
            matrix = [list(map(int, input().split())) for _ in range(n)]
            dist = min_distance(n, m, matrix)
            for row in dist:
                print(*row)
        else:
            print("Datele de intrare nu corespund restrictiilor impuse.")
    except ValueError:
        print("Datele de intrare nu corespund restrictiilor impuse.")
    except IndexError:
        print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>