labirint3

#include <bits/stdc++.h>
#define NMAX 1010
using namespace std;

ifstream fin("labirint.in");
ofstream fout("labirint.out");

char L[NMAX][NMAX];
int DA[NMAX][NMAX], DC[NMAX][NMAX];
bool VIZ[NMAX][NMAX],gasit;
int dl[]= {-1,0,1,0};
int dc[]= {0,1,0,-1};

struct poz
{
    int l,c;
};
poz C1[NMAX*NMAX], C2[NMAX*NMAX];
int n,m;

int main()
{
    int i,j,k,pa,ua,pc,uc,d1,d2=1000000;
    poz x,v;
    pa=ua=0;
    pc=uc=0;
    gasit=false;

    //citire si creare cozi
    fin>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            fin>>L[i][j];
            if(L[i][j]=='A')
            {
                DA[i][j]=1;
                C1[ua].l=i;
                C1[ua].c=j;
                ua++;
            }
            else if(L[i][j]=='C')
            {
                DC[i][j]=1;
                C2[uc].l=i;
                C2[uc].c=j;
                uc++;
            }
        }


    //bordare
    for (i=0; i<=m+1; i++) DA[0][i]=DA[n+1][i]=-1;
    for (i=0; i<=n+1; i++) DA[i][0]=DA[i][m+1]=-1;
    for (i=0; i<=m+1; i++) DC[0][i]=DC[n+1][i]=-1;
    for (i=0; i<=n+1; i++) DC[i][0]=DC[i][m+1]=-1;

    //rezolvare
    while ((pa<ua || pc<uc) && gasit==false)
    {
        if(pa<ua){
        x=C1[pa];
        pa++;
        for (k=0; k<4; k++)
        {
            v.l=x.l+dl[k];
            v.c=x.c+dc[k];

            if (DA[v.l][v.c]==0 && L[v.l][v.c]!='Z')
            {
                DA[v.l][v.c]=DA[x.l][x.c]+1;

                C1[ua]=v;ua++;
                if(L[v.l][v.c]=='B')
                {
                   if (VIZ[v.l][v.c]==false)
                    {VIZ[v.l][v.c]=true;}
                   else
                    {d1=DA[v.l][v.c]+DC[v.l][v.c]; if(d1<d2) d2=d1; cout<<d1<<"\n";}
                }

            }
        }
        }
        if(pc<uc){
        x=C2[pc];
        pc++;
        for (k=0; k<4; k++)
        {
            v.l=x.l+dl[k];
            v.c=x.c+dc[k];

            if (DC[v.l][v.c]==0 && L[v.l][v.c]!='Z')
            {
                DC[v.l][v.c]=DC[x.l][x.c]+1;

                C2[uc]=v;uc++;
                if(L[v.l][v.c]=='B')
                {

                   if (VIZ[v.l][v.c]==false)
                    VIZ[v.l][v.c]=true;
                   else
                    {d1=DC[v.l][v.c]+DA[v.l][v.c];if(d1<d2) d2=d1;cout<<d1<<"\n";}
                }

            }
        }
        }

    }

fout<<d2-1<<endl;
fout.close();

return 0;

}