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

Exemplu:

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

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

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 min_distance(n, m, matrix):

   # Definim directiile in care putem merge (sus, jos, stanga, dreapta)
   dx = [-1, 0, 1, 0]
   dy = [0, 1, 0, -1]

   # Initializam o matrice de vizitare si o matrice de distante
   visited = [[False]*m for _ in range(n)]
   dist = [[0]*m for _ in range(n)]

   # Cream o coada pentru BFS
   q = deque()

   # Parcurgem matricea si adaugam in coada toate celulele care au cel putin un vecin cu valoare diferita
   for i in range(n):
       for j in range(m):
           if any(matrix[i][j] != matrix[i+dx[k]][j+dy[k]] for k in range(4) if 0 <= i+dx[k] < n and 0 <= j+dy[k] < m):
               q.append((i, j))
               visited[i][j] = True

   # Parcurgem coada si actualizam distantele pentru toate celulele nevizitate
   while q:
       x, y = q.popleft()
       for k in range(4):
           nx, ny = x + dx[k], y + dy[k]
           if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
               dist[nx][ny] = dist[x][y] + 1
               q.append((nx, ny))
               visited[nx][ny] = True

   return dist

1. Citim dimensiunile matricei si matricea

n, m = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(n)]

1. Calculam distantele minime

dist = min_distance(n, m, matrix)

1. Afisam distantele

for row in dist:

   print(*row)

</syntaxhighlight>