# PBinfo #3949 – mindist – Rezolvare C++

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

## Enunț

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

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define N_MAX 1000
#define K_MAX 100000
#define INF (INT_MAX >> 1)
using namespace std;
ifstream fin("mindist.in");
ofstream fout("mindist.out");
int N, M, K;
queue < pair <int, int> > Q;
bool is_blocked[N_MAX + 5][N_MAX + 5];
int D[N_MAX + 5][N_MAX + 5];
int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, 1, -1};
bool OK(int i, int j) {
    return i >= 1 && i <= N && j >= 1 && j <= N;
}
int main()
{
    fin >> N >> M >> K;
    while(M--) {
        int x, y;
        fin >> x >> y;
        is_blocked[x][y] = true;
    }
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            D[i][j] = INF;
        }
    }
    for(int i = 1; i <= K; i++) {
        int x, y;
        fin >> x >> y;
        D[x][y] = 0;
        Q.push({x, y});
    }
    while(!Q.empty()) {
        int i = Q.front().first;
        int j = Q.front().second;
        Q.pop();
        for(int d = 0; d < 4; d++) {
            int ii = i + di[d];
            int jj = j + dj[d];
            if(OK(ii, jj) && D[ii][jj] > 1 + D[i][j] && !is_blocked[ii][jj]) {
                D[ii][jj] = 1 + D[i][j];
                Q.push({ii, jj});
            }
        }
    }
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            fout << (D[i][j] == INF ? -1 : D[i][j]) << " ";
        }
        fout << "\n";
    }
    return 0;
}
```

## Resurse

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