#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],d[N][N],u[N][N],r[N][N],l[N][N],exist[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;
}


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;
                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;
    }
    /*

    ///m=2
    memset(d,false,sizeof(d));
    memset(d,false,sizeof(u));
    memset(d,false,sizeof(l));
    memset(d,false,sizeof(r));
    ///calc d
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int t=i;t<=i+k+1;t++){
                if(ok2(t,j-k-1)){
                    if(canB[t][j-k-1])d[i][j]=true;
                }
            }
            for(int t=j-k-1;t<=j+k+1;t++){
                if(ok2(i+k+1,t)){
                    if(canB[i+k+1][t])d[i][j]=true;
                }
            }
            for(int t=i;t<=i+k+1;t++){
                if(ok2(t,j+k+1)){
                    if(canB[t][j+k+1])d[i][j]=true;
                }
            }
        }
    }

    ///calc u
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int t=i-k-1;t<=i;t++){
                if(ok2(t,j-k-1)){
                    if(canB[t][j-k-1])u[i][j]=true;
                }
            }
            for(int t=j-k-1;t<=j+k+1;t++){
                if(ok2(i-k-1,t)){
                    if(canB[i-k-1][t])u[i][j]=true;
                }
            }
            for(int t=i-k-1;t<=i;t++){
                if(ok2(t,j+k+1)){
                    if(canB[t][j+k+1])u[i][j]=true;
                }
            }
        }
    }

    ///calc l
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int t=j-k-1;t<=j;t++){
                if(ok2(i-k-1,t)){
                    if(canB[i-k-1][t])l[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])l[i][j]=true;
                }
            }
            for(int t=j-k-1;t<=j;t++){
                if(ok2(i+k+1,t)){
                    if(canB[i+k+1][t])l[i][j]=true;
                }
            }
        }
    }

    ///calc r
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int t=j;t<=j+k+1;t++){
                if(ok2(i-k-1,t)){
                    if(canB[i-k-1][t])r[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])r[i][j]=true;
                }
            }
            for(int t=j;t<=j+k+1;t++){
                if(ok2(i+k+1,t)){
                    if(canB[i+k+1][t])r[i][j]=true;
                }
            }
        }
    }
    cout<<endl<<endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<l[i][j];
        }
        cout<<endl;
    }
    cout<<endl<<endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<r[i][j];
        }
        cout<<endl;
    }
    cout<<endl<<endl;

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<d[i][j];
        }
        cout<<endl;
    }
    cout<<endl<<endl;

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<u[i][j];
        }
        cout<<endl;
    }
    */
    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;
                        //if(u[i-k][t]||d[i-k][t]||l[i-k][t]||r[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;
                        //if(u[i+k][t]||d[i+k][t]||l[i+k][t]||r[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;
                        //if(u[t][j-k]||d[t][j-k]||l[t][j-k]||r[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;
                        //if(u[t][j+k]||d[t][j+k]||l[t][j+k]||r[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]});
            }
        }
    }

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

    cout<<endl<<endl;

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

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

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

    //solve(3);

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

    cout<<ans;
    return 0;
}