# PBinfo #3375 – labirint3 – Rezolvare C++

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

## Enunț

Vasilică vizitează cetățile medievale. Fiind curios, el încearcă să descopere pasajele secrete și ascunzătorile. Din nefericire, s-a rătăcit și a ajuns într-o sală din care nu poate ieși decât trecând printr-un labirint. Există o hartă a labirintului, o matrice de n linii și m coloane, un element din această matrice reprezentând o cameră. Deplasarea în labirint se poate face numai prin camerele adiacente pe orizontală și verticală. Intrările în labirint sunt notate cu A, ieșirile cu C, iar camerele zidite (inaccesibile) cu Z. Ieșirea din labirint se poate face din una din camerele C, în fiecare astfel de cameră existând câte un elicopter încuiat. Toate elicopterele se deschid cu aceeași cheie, câte un exemplar al cheii aflându-se în camerele B. Trecerea în altă cameră va dura 1 unitate de timp. Pentru a ieși din labirint Vasilică intră pe una din intrările notate cu A, ia cheia dintr-o cameră B și iese din labirint printr-o cameră C. El va intra în camera A la timpul 1. Camerele de tip A pot fi situate oriunde pe hartă. În drumul de la o cameră de tip A către o cameră de tip B se poate trece printr-o cameră de tip C fără a se ieși din labirint.

Cerința
Ajutați-l pe Vasilică să iasă cât mai repede din labirint.

Date de intrare
Fișierul de intrare labirint.in conține pe prima linie numărul n de linii şi numărul m de coloane ale hărții, iar pe următoarele n linii, câte m caractere, reprezentând elementele acesteia. Caracterele pot fi _, A, B, C, Z cu semnificația din text. _ reprezintă o cameră fără restricții (liberă).

Date de ieșire
Pe prima linie a fişierului de ieşire labirint.out se va scrie numărul ce reprezintă timpul cel mai scurt în care Vasilică poate să iasă din labirint.

Restricții și precizări

1 ≤  n, m  ≤ 1000
întotdeauna există un drum de ieșire
operația de luare a cheii sau a elicopterului dintr-o cameră nu consumă timp

Exemplu:
labirint.in

5 6
ZA____
A__Z__
A_C__B
C___Z_
___B_Z
labirint.out

9
Explicație
Timpul cel mai scurt în care Vasilică poate să iasă din labirint este de 9 unități și avem două variante: plecăm din A(3,1) la timpul 1 și ajungem în B(3,6) sau în B(5,4) la timpul 6 (luăm cheia) și ieșim prin C(3,3) la timpul 9.

## Cod sursă C++

```cpp
#include <fstream>
#include<queue>
#define VM 100000000
using namespace std;
ifstream fin("labirint.in");
ofstream fout("labirint.out");
char a[1002][1002];
struct poz
{
    int x,y;
};
int n,m,b[1002][1002],c[1002][1002];
int dx[4]= {-1,0,1,0};
int dy[4]= {0,1,0,-1};
queue<poz>q;
int main()
{
    int i,j,k,w,dm=VM;
    fin>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            fin>>a[i][j];
///bordare
    for(j=0; j<=m+1; j++)
        a[0][j]=a[n+1][j]='Z';
    for(i=0; i<=n+1; i++)
        a[i][0]=a[i][m+1]='Z';
///matricea b
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(a[i][j]=='A')
            {
                b[i][j]=1;
                q.push({i,j});
            }
    poz p1,p2;
    while(!q.empty())
    {
        p1=q.front();
        q.pop();
        for(k=0; k<4; k++)
        {
            p2.x=p1.x+dx[k];
            p2.y=p1.y+dy[k];
            if(a[p2.x][p2.y]!='Z' && b[p2.x][p2.y]==0)
            {
                w=b[p1.x][p1.y]+1;
                b[p2.x][p2.y]=w;
                q.push(p2);
            }
        }
    }
    ///matricea c
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(a[i][j]=='C')
            {
                c[i][j]=1;
                q.push({i,j});
            }
    while(!q.empty())
    {
        p1=q.front();
        q.pop();
        for(k=0; k<4 ; k++)
        {
            p2.x=p1.x+dx[k];
            p2.y=p1.y+dy[k];
            if(a[p2.x][p2.y]!='Z' && c[p2.x][p2.y]==0)
            {
                w=c[p1.x][p1.y]+1;
                c[p2.x][p2.y]=w;
                q.push(p2);
            }
        }
    }
///final
    dm=VM;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(a[i][j]=='B' && b[i][j]>0 && c[i][j]>0
               && b[i][j]+c[i][j]<dm)
                dm=b[i][j]+c[i][j];
    fout<<dm-1<<endl;
    return 0;
}
```

## Resurse

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