#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
const int N = 505;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};

int n,m,xa,xb,ya,yb;
bool canA[N][N],canB[N][N];
int sum[N][N];
string s[N];

bool ok(int x,int y){
    if(x<0||x>=n||y<0||y>=n||s[x][y]!='.')return false;
    return true;
}

bool ok2(int x,int y){
    if(x<0||x>=n||y<0||y>=n)return false;
    return true;
}

int getsum(int x1,int y1,int x2,int y2){
    if(x1<0)x1=0;
    if(x1>=n)x1=n-1;
    if(x2<0)x2=0;
    if(x2>=n)x2=n-1;
    if(y1<0)y1=0;
    if(y1>=n)y1=n-1;
    if(y2<0)y2=0;
    if(y2>=n)y2=n-1;

    int ra=sum[x2][y2];
    int rb=0,rc=0,rd=0;

    if(y1-1>=0)rb=sum[x2][y1-1];
    if(x1-1>=0)rc=sum[x1-1][y2];
    if(x1-1>=0&&y1-1>=0)rd=sum[x1-1][y1-1];

    //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<"--->  "<<ra-rb-rc+rd<<endl;

    return ra-rb-rc+rd;
}

bool solve(int k){
    if(m==1){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(!canA[i][j])continue;
                int s=getsum(i-k-1,j-k-1,i+k+1,j+k+1);
                if(s>0)return true;
            }
        }
        return false;
    }
     for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!canA[i][j])continue;
            //cout<<"working for "<<i<<" "<<j<<endl;
            for(int t=j-k;t<=j+k;t++){
                if(ok2(i-k,t)){
                    int posx=i-k;
                    int posy=t;
                    //cout<<posx<<" "<<posy<<endl;
                    //cout<<posx-k-1<<" "<<posy-k-1<<" "<<posx+k+1<<" "<<posy+k+1<<"                       ";
                    int s=getsum(posx-k-1,posy-k-1,posx+k+1,posy+k+1);

                    if(s>0)return true;
                }

            }
            for(int t=j-k;t<=j+k;t++){
                if(ok2(i+k,t)){
                    int posx=i+k;
                    int posy=t;
                   // cout<<posx<<" "<<posy<<endl;
                   // cout<<posx-k-1<<" "<<posy-k-1<<" "<<posx+k+1<<" "<<posy+k+1<<"                       ";
                    int s=getsum(posx-k-1,posy-k-1,posx+k+1,posy+k+1);
                    if(s>0)return true;
                }
            }
            for(int t=i-k;t<=i+k;t++){
                if(ok2(t,j-k)){
                    int posx=t;
                    int posy=j-k;
                   // cout<<posx<<" "<<posy<<endl;
                   //  cout<<posx-k-1<<" "<<posy-k-1<<" "<<posx+k+1<<" "<<posy+k+1<<"                       ";
                    int s=getsum(posx-k-1,posy-k-1,posx+k+1,posy+k+1);
                    if(s>0)return true;
                }

            }
            for(int t=i-k;t<=i+k;t++){
                if(ok2(t,j+k)){
                    int posx=t;
                    int posy=j+k;
                   // cout<<posx<<" "<<posy<<endl;
                    // cout<<posx-k-1<<" "<<posy-k-1<<" "<<posx+k+1<<" "<<posy+k+1<<"                       ";
                    int s=getsum(posx-k-1,posy-k-1,posx+k+1,posy+k+1);
                    if(s>0)return true;
                }
            }
        }
    }
    return false;
}

/*bool solvee(int k){
    if(m==1){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(!canA[i][j])continue;
                bool sol=false;
                for(int t=j-k-1;t<=j+k+1;t++){
                    if(ok2(i-k-1,j)){
                        if(canB[i-k-1][j]){
                            return true;
                        }
                    }
                }
                for(int t=j-k-1;t<=j+k+1;t++){
                    if(ok2(i+k+1,j)){
                        if(canB[i+k+1][j]){
                            return true;
                        }
                    }
                }
                for(int t=i-k-1;t<=i+k+1;t++){
                    if(ok2(t,j-k-1)){
                        if(canB[t][j-k-1]){
                            return true;
                        }
                    }
                }
                for(int t=i-k-1;t<=i+k+1;t++){
                    if(ok2(t,j+k+1)){
                        if(canB[t][j+k+1]){
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    memset(exist,false,sizeof(exist));
    for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                for(int t=j-k-1;t<=j+k+1;t++){
                    if(ok2(i-k-1,j)){
                        if(canB[i-k-1][j]){
                            exist[i][j]=true;
                        }
                    }
                }
                for(int t=j-k-1;t<=j+k+1;t++){
                    if(ok2(i+k+1,j)){
                        if(canB[i+k+1][j]){
                            exist[i][j]=true;
                        }
                    }
                }
                for(int t=i-k-1;t<=i+k+1;t++){
                    if(ok2(t,j-k-1)){
                        if(canB[t][j-k-1]){
                            exist[i][j]=true;
                        }
                    }
                }
                for(int t=i-k-1;t<=i+k+1;t++){
                    if(ok2(t,j+k+1)){
                        if(canB[t][j+k+1]){
                            exist[i][j]=true;
                        }
                    }
                }
            }
        }


    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(canA[i][j]){
                for(int t=j-k;t<=j+k;t++){
                    if(ok2(i-k,t)){
                        if(exist[i-k][t])return true;
                    }
                }
                for(int t=j-k;t<=j+k;t++){
                    if(ok2(i+k,t)){
                        if(exist[i+k][t])return true;
                    }
                }
                for(int t=i-k;t<=i+k;t++){
                    if(ok2(t,j-k)){
                        if(exist[t][j-k])return true;
                    }
                }
                for(int t=i-k;t<=i+k;t++){
                    if(ok2(t,j+k)){
                        if(exist[t][j+k])return true;
                    }
                }
            }
        }
    }
    return false;
}*/

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
        for(int j=0;j<n;j++){
            if(s[i][j]=='A'){
                xa=i;
                ya=j;
            }else if(s[i][j]=='B'){
                xb=i;
                yb=j;
            }
        }
    }

    queue<pair<int,int> >q;
    q.push({xa,ya});
    while(!q.empty()){
        auto e=q.front();
        canA[e.first][e.second]=true;
        q.pop();
        for(int i=0;i<4;i++){
            if(ok(e.first+dx[i],e.second+dy[i])&&!canA[e.first+dx[i]][e.second+dy[i]]){
                q.push({e.first+dx[i],e.second+dy[i]});
            }
        }
    }

    q.push({xb,yb});
    while(!q.empty()){
        auto e=q.front();
        canB[e.first][e.second]=true;
        q.pop();
        for(int i=0;i<4;i++){
            if(ok(e.first+dx[i],e.second+dy[i])&&!canB[e.first+dx[i]][e.second+dy[i]]){
                q.push({e.first+dx[i],e.second+dy[i]});
            }
        }
    }

    if(canA[xb][yb]){
        cout<<-1;
        return 0;
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==0){
                if(j==0){
                    sum[i][j]=canB[i][j];
                }else{
                    sum[i][j]=sum[i][j-1]+canB[i][j];
                }
            }else{
                if(j==0){
                    sum[i][j]=sum[i-1][j]+canB[i][j];
                }else{
                    sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+canB[i][j];
                }
            }
        }
    }

    /*for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<sum[i][j]<<" ";
        }
        cout<<endl;
    }*/




    int lo=1;
    int hi=n;
    int ans=n;

    solve(1);

    while(lo<=hi){
        int mid=(lo+hi)>>1;
        if(solve(mid)){
            ans=mid;
            hi=mid-1;
        }else{
            lo=mid+1;
        }
    }

    cout<<ans;
    return 0;
}