# PBinfo #3277 – Lee – Rezolvare C++

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

## Enunț

Se consideră o matrice cu N linii și N coloane, numerotate de la 1 la N, care memorează doar valori 0 și 1. Se dau de asemenea coordonatele a trei componente din această matrice.

Cerința
Să se determine lungimea minimă a unui drum care pleacă din poziția (1,1), trece obligatoriu prin cele trei componente date (nu contează în ce ordine) și apoi ajunge în poziția (N, N), drum care trece doar prin componente marcate cu 0 și învecinate pe linii și coloane. Un pas din drum constă din deplasarea dintr-un punct (i,j) într-unul din cele patru învecinate pe linie și coloană, adică într-unul din punctele (i-1,j), (i,j-1), (i+1, j), (i,j+1).

Date de intrare
Programul citește de la tastatură numărul N. Pe fiecare din următoarele N linii și N coloane este descrisă matricea binară. Pe ultimele trei linii sunt câte două numere naturale de forma x y ce descriu coordonatele în matrice (linie și coloană) ale celor trei puncte.

Date de ieșire
Programul va afișa pe ecran un singur număr natural, care reprezintă lungimea minimă a drumului care pornește din (1, 1), trece prin cele trei puncte date și ajunge în punctul (N, N).

Restricții și precizări

3 ≤ N ≤ 100
Cele trei puncte sunt distincte, diferite de pozițiile (1,1) și (N,N) și se găsesc la poziții din matrice marcate cu 0. De asemenea, la pozițiile (1,1) și (N,N) se găsește mereu valoarea 0.
Pentru datele de intrare va exista mereu soluție, adică există cel puțin un drum de la (1,1) la (N,N).

Exemplu:
Intrare

4
0 0 0 0
1 0 1 1
0 0 0 1
1 0 0 0
3 3
1 4
3 1
Ieșire

12
Explicație
Cele trei puncte sunt situate în coordonatele (3,3), (1,4), (3,1).
Drumul de lungime minimă este:


de la (1,1) la (1,4) (lungime 3)
de la (1,4) la (3,1) (lungime 5)
de la (3,1) la (3,3) (lungime 2)
de la (3,3) la (4,4) (lungime 2)
Lungime totală: 3 + 5 + 2 + 2 = 12.

## Cod sursă C++

```cpp
#include<bits/stdc++.h>
using namespace std;
int a[105][105], n;
int d1[105][105];
int d2[105][105];
int d3[105][105];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
pair<int, int> A[4];
queue< pair<int, int> > q;
void Init()
{
    int i, j;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            d1[i][j] = d2[i][j] = d3[i][j] = 1000000;
}
void Bordare()
{
    int i;
    for (i = 0; i <= n + 1; i++)
        a[0][i] = a[i][0] = a[n + 1][i] = a[i][n + 1] = 1;
}
void Lee(int x, int y, int d[105][105])
{
    int i, j, k;
    d[x][y] = 0;
    q.push({x, y});
    while (!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (k = 0; k < 4; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (a[x][y] == 0 && d[x][y] > d[i][j] + 1)
            {
                d[x][y] = 1 + d[i][j];
                q.push({x, y});
            }
        }
    }
}
void Afisare()
{
    int M = 1000000;
    /// (1,1) - A - B - C - (n,n)
    M = min(M, d1[1][1] + d1[A[2].first][A[2].second] +
            d3[A[2].first][A[2].second] + d3[n][n]);
    /// (1,1) - A - C - B - (n,n)
    M = min(M, d1[1][1] + d1[A[3].first][A[3].second] +
            d2[A[3].first][A[3].second] + d2[n][n]);
    /// (1,1) - B - A - C - (n,n)
    M = min(M, d2[1][1] + d2[A[1].first][A[1].second] +
            d3[A[1].first][A[1].second] + d3[n][n]);
    /// (1,1) - B - C - A - (n,n)
    M = min(M, d2[1][1] + d2[A[3].first][A[3].second] +
            d1[A[3].first][A[3].second] + d1[n][n]);
    /// (1,1) - C - A - B - (n,n)
    M = min(M, d3[1][1] + d3[A[1].first][A[1].second] +
            d2[A[1].first][A[1].second] + d2[n][n]);
    /// (1,1) - C - B - A - (n,n)
    M = min(M, d3[1][1] + d3[A[2].first][A[2].second] +
            d1[A[2].first][A[2].second] + d1[n][n]);
    cout << M;
}
void Citire()
{
    int i, j;
    cin >> n;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            cin >> a[i][j];
    for (i = 1; i <= 3; i++)
        cin >> A[i].first >> A[i].second;
}
int main()
{
    Citire();
    Bordare();
    Init();
    Lee(A[1].first, A[1].second, d1);
    Lee(A[2].first, A[2].second, d2);
    Lee(A[3].first, A[3].second, d3);
    Afisare();
    return 0 ;
}
```

## Resurse

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