#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

int N;
int smerX[]={1,0,-1,0},
    smerY[]={0,1,0,-1};

bool pored_zida(std::vector<std::vector<char> > &mat, int &x, int &y)
{
    for(int i=0; i<4; i++) if(mat[y+smerY[i]][x+smerX[i]]=='X') return true;
    return false;
}

int avr(int br) { return br<0 ? -br : br; }

int kvadrat(int &ax, int &ay, int &bx, int &by)
{
    int avx=avr(ax-bx), avy=avr(ay-by), r;
    if(avx==avy) r=avx;
    else r=std::max(avr(ax-bx), avr(ay-by))-1;
    return r;
}

bool nadji_put(std::vector<std::vector<char> > &mat, int &ax, int &ay, int &bx, int &by, int &b1x, int &b1y, int &b2x, int &b2y, int &k)
{
    std::vector<std::vector<bool> > bmat1(2*k+1, std::vector<bool>(2*k+1, false)), bmat2(2*k+1, std::vector<bool>(2*k+1, false));
    int kx, ky;
    kx=b1x+k;
    ky=b1y+k;
    for(int i=b1y-k; i<=ky; i++) for(int j=b1x-k; j<=kx; j++) if(i>0 && i<N+1 && j>0 && j<N+1 && mat[i][j]=='X')
    {
        mat[i][j]='.';
        bmat1[i-b1y+k][j-b1x+k]=true;
    }
    kx=b2x+k;
    ky=b2y+k;
    for(int i=b2y-k; i<=ky; i++) for(int j=b2x-k; j<=kx; j++) if(i>0 && i<N+1 && j>0 && j<N+1 && mat[i][j]=='X')
    {
        mat[i][j]='.';
        bmat1[i-b2y+k][j-b2x+k]=true;
    }
    std::queue<int> red;
    int x, y, tx, ty;
    red.push(ax);
    red.push(ay);
    while(!red.empty())
    {
        x=red.front(); red.pop();
        y=red.front(); red.pop();
        for(int i=0; i<4; i++)
        {
            tx=x+smerX[i];
            ty=y+smerY[i];
            if(tx>0 && tx<N+1 && ty>0 && ty<N+1 && mat[ty][tx]=='.')
            {
                red.push(tx);
                red.push(ty);
            }
            if(tx==bx && ty==by) return true;
        }
    }
    kx=b1x+k;
    ky=b1y+k;
    for(int i=b1y-k; i<=ky; i++) for(int j=b1x-k; j<=kx; j++) if(i>0 && i<N+1 && j>0 && j<N+1 && bmat1[i-b1y+k][j-b1x+k]) mat[i][j]='X';
    kx=b2x+k;
    ky=b2y+k;
    for(int i=b2y-k; i<=ky; i++) for(int j=b2x-k; j<=kx; j++) if(i>0 && i<N+1 && j>0 && j<N+1 && bmat1[i-b2y+k][j-b2x+k]) mat[i][j]='X';
    return false;
}

int main()
{
    std::ios::sync_with_stdio(false);
    int M;
    std::cin >> N >> M;
    std::vector<std::vector<char> > mat(N+2, std::vector<char>(N+2));
    for(int i=0; i<N+2; i++)
    {
        mat[i][0]='C';
        mat[i][N+1]='C';
        mat[0][i]='C';
        mat[0][N+1]='C';
    }
    char ch;
    int Ax, Ay, Bx, By;
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++)
    {
        std::cin >> ch;
        if(ch=='A')
        {
            Ax=j;
            Ay=i;
        }
        else if(ch=='B')
        {
            Bx=j;
            By=i;
        }
        else mat[i][j]=ch;
    }
    //std::cout << Ax << " " << Ay << "\n" << Bx << " " << By;
    std::vector<int> A, B;
    std::queue<int> red;
    red.push(Ax);
    red.push(Ay);
    int x, y, tx, ty;
    std::vector<std::vector<bool> > bmat(N+2, std::vector<bool>(N+2, true));
    bool kraj=false;
    while(!red.empty() && !kraj)
    {
        x=red.front(); red.pop();
        y=red.front(); red.pop();
        for(int i=0; i<4; i++)
        {
            tx=x+smerX[i];
            ty=y+smerY[i];
            if(tx>0 && tx<N+2 && ty>0 && ty<N+2 && bmat[ty][tx])
            {
                if(mat[ty][tx]=='.')
                {
                    bmat[ty][tx]=false;
                    red.push(tx);
                    red.push(ty);
                    if(pored_zida(mat, tx, ty))
                    {
                        A.push_back(tx);
                        A.push_back(ty);
                    }
                }
                else if(mat[ty][tx]=='B')
                {
                    kraj=true;
                    break;
                }
            }
        }
    }
    if(A.size()==0)
    {
        A.push_back(Ax);
        A.push_back(Ay);
    }
    //int k=A.size(); for(int i=0; i<k; i+=2) std::cout << A[i] << " " << A[i+1] << "\n";
    if(kraj) std::cout << "-1";
    else
    {
        red.push(Bx);
        red.push(By);
        while(!red.empty())
        {
            x=red.front(); red.pop();
            y=red.front(); red.pop();
            for(int i=0; i<4; i++)
            {
                tx=x+smerX[i];
                ty=y+smerY[i];
                if(tx>0 && tx<N+2 && ty>0 && ty<N+2 && mat[ty][tx]=='.' && bmat[ty][tx])
                {
                    bmat[ty][tx]=false;
                    red.push(tx);
                    red.push(ty);
                    if(pored_zida(mat, tx, ty))
                    {
                        B.push_back(tx);
                        B.push_back(ty);
                    }
                }
            }
        }
        if(B.size()==0)
        {
            B.push_back(Bx);
            B.push_back(By);
        }
        int MIN=1001, r, a, b;
        for(int i=0; i<A.size(); i+=2) for(int j=0; j<B.size(); j+=2)
        {
            r=kvadrat(A[i], A[i+1], B[j], B[j+1]);
            if(r<MIN)
            {
                MIN=r;
                a=i;
                b=j;
            }
        }
        if(M==2)
        {
            //std::cout << "m=2";
            for(int i=1; i<=50; i++) if(nadji_put(mat, Ax, Ay, Bx, By, A[a], A[a+1], B[b], B[b+1], i))
            {
                r=i;
                break;
            }
        }
        else r=MIN;
        std::cout << r;
    }// kraj else
    return 0;
}