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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema labirint3:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3375 labirint3

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3375 labirint3 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3375 labirint3