# PBinfo #4052 – emigrare – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Tărâmul emigranților se poate reprezenta printr-o matrice de dimensiuni \(n\times 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ă \(a_{i,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ă \(d_{i,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 \le n,m \le 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 \le 10\)
Pentru 40 de puncte, \(n,m \le 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\).

## Cod sursă C++

```cpp
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NM_MAX = 1000;
int n, m;
int mat[NM_MAX + 2][NM_MAX + 2];
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};
bool inside (int i, int j) {
    return (1 <= i && i <= n && 1 <= j && j <= m);
}
int dist[NM_MAX + 2][NM_MAX + 2];
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mat[i][j];
        }
    }
    queue <pair <int, int>> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dist[i][j] = -1;
            for (int d = 0; d < 4; d++) {
                int i1 = i + di[d], j1 = j + dj[d];
                if (inside(i1, j1) == true && mat[i][j] != mat[i1][j1]) {
                    dist[i][j] = 0;
                    break;
                }
            }
            if (dist[i][j] == 0) {
                q.push(make_pair(i, j));
            }
        }
    }
    while (q.empty() == false) {
        int i, j;
        tie(i, j) = q.front();
        q.pop();
        for (int d = 0; d < 4; d++) {
            int i1 = i + di[d], j1 = j + dj[d];
            if (inside(i1, j1) == true && dist[i1][j1] == -1) {
                dist[i1][j1] = dist[i][j] + 1;
                q.push(make_pair(i1, j1));
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4052)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4052/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4052/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)