#include<cstdio>
#include<vector>
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#define lld long long
#define pb push_back
#include<queue>
#define ff first
#define ss second
using namespace std;
//int dx[8]={0,0,1,1,1,-1,-1,-1};
//int dy[8]={1,-1,1,0,-1,1,0,-1};

int dx[8]={0,0,1,-1,1,-1,1,-1};
int dy[8]={1,-1,0,0,-1,1,1,-1};
vector<pair<int,int> >vect[3];
pair<int,int>apos,bpos;
int cola,colb,pos[510][510],m,adist[510][510],adist2[510][510],bdist[510][510],rez,adist3[510*510];
char mat[510][510];
int col[510][510],clr,n;
void dfs(int x,int y){
    col[x][y]=clr;
    for(int i=0;i<4;i++){
        int idx=x+dx[i];
        int idy=y+dy[i];
        if(idx<1 || idx>n || idy<1 || idy>n || col[idx][idy] || mat[idx][idy]=='X')continue;
        dfs(idx,idy);
    }
}
void color(){

   for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(col[i][j] || mat[i][j]=='X')continue;
        clr++;
        dfs(i,j);
    }
   }

}
void select(){
   for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){

       if(col[i][j]==cola)vect[1].pb({i,j});
       if(col[i][j]==colb)vect[2].pb({i,j});

    }
   }
}
void bfs(pair<int,int> x,int dp[][510],int pc){

   queue<pair<int,int> >q;
   memset(pos,0,sizeof(pos));
   for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)dp[i][j]=2;

   for(int i=0;i<vect[pc].size();i++){
      int idx=vect[pc][i].ff;
      int idy=vect[pc][i].ss;
      q.push({idx,idy});
      pos[idx][idy]=1;
      dp[idx][idy]=0;
   }

   while(q.size()){

       x=q.front();
       q.pop();
       int dist=dp[x.ff][x.ss];
       if(dist==1)continue;

       for(int i=0;i<4;i++){
        int idx=x.ff+dx[i];
        int idy=x.ss+dy[i];
        if(pos[idx][idy] || idx<1 ||idx>n || idy<1 || idy>n)continue;

        dp[idx][idy]=dist+1;
        pos[idx][idy]=1;
        q.push({idx,idy});
       }

   }

//   for(int i=1;i<=n;i++){
//    for(int j=1;j<=n;j++)printf("%d ",dp[i][j]);
//    printf("\n");
//   }


   for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)if(dp[i][j]==1)dp[i][j]=0;

   for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)if(dp[i][j]==0)q.push({i,j});

   while(q.size()){

       x=q.front();
       q.pop();
       int dist=dp[x.ff][x.ss];

       for(int i=0;i<8;i++){
        int idx=x.ff+dx[i];
        int idy=x.ss+dy[i];
        if(pos[idx][idy] || idx<1 ||idx>n || idy<1 || idy>n)continue;

        dp[idx][idy]=dist+1;
        pos[idx][idy]=1;
        q.push({idx,idy});
       }

   }

}
void bfs2(pair<int,int> x,int dp[][510],int pc){

   queue<pair<int,int> >q;
   memset(pos,0,sizeof(pos));

   for(int i=0;i<vect[pc].size();i++){
      int idx=vect[pc][i].ff;
      int idy=vect[pc][i].ss;
      q.push({idx,idy});
      pos[idx][idy]=1;
      dp[idx][idy]=0;
   }


   while(q.size()){

       x=q.front();
       q.pop();
       int dist=dp[x.ff][x.ss];

       for(int i=0;i<8;i++){
        int idx=x.ff+dx[i];
        int idy=x.ss+dy[i];
        if(pos[idx][idy] || idx<1 ||idx>n || idy<1 || idy>n)continue;

        dp[idx][idy]=dist+1;
        pos[idx][idy]=1;
        q.push({idx,idy});
       }

   }

}
bool check1(int x){

    for(int i=0;i<vect[1].size();i++){
        int idx=vect[1][i].ff;
        int idy=vect[1][i].ss;
        if(bdist[idx][idy]<=x)return 1;
    }
return 0;
}
bool check2(int x){

   if(m<2)return 0;

   for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(mat[i][j]=='X'){
            if(adist2[i][j]<=x && bdist[i][j]<=x)return 1;
        }
        else if(adist3[col[i][j]]<=x && bdist[i][j]<=x)return 1;
    }
   }
return 0;
}
int main(){

//    freopen("test.txt","r",stdin);

    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(int j=1;j<=n;j++){
            mat[i][j]=s[j-1];
            if(s[j-1]=='A')apos={i,j};
            if(s[j-1]=='B')bpos={i,j};
        }
    }

    color();
    cola=col[apos.ff][apos.ss];
    colb=col[bpos.ff][bpos.ss];
    select();

    bfs(apos,adist,1);
    bfs2(apos,adist2,1);
    bfs(bpos,bdist,2);
//
//        for(int i=1;i<=n;i++){
//    for(int j=1;j<=n;j++){
// printf("%d ",col[i][j]);
//    }
//    printf("\n");}
//
    for(int i=1;i<=clr;i++)adist3[i]=1e9;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){

         if(!col[i][j])continue;

             for(int p=0;p<4;p++){

                int idx=i+dx[p];
                int idy=j+dy[p];

                if(idx<1 || idy<1 || idx>n || idy>n)continue;

                adist3[col[i][j]]=min(adist3[col[i][j]],adist2[idx][idy]);

             }


        }
    }

//    for(int i=1;i<=clr;i++)printf("%d  dist\n",adist3[i]);

//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=n;j++)printf("%d ",adist[i][j]);
//        printf("\n");
//    }
//printf("\n");
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=n;j++)printf("%d ",bdist[i][j]);
//        printf("\n");
//    }
//    printf("\n");
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=n;j++)printf("%d ",adist2[i][j]);
//        printf("\n");
//    }

    int l=0;
    int r=n;
    int sr;
    while(l<=r){
        sr=(l+r)/2;
        if(check1(sr) || check2(sr)){
            r=sr-1;
            rez=sr;
        }
        else l=sr+1;
    }

//    printf("%d\n",check2(1));

    if(rez==0)printf("-1\n");
    else printf("%d\n",rez);

return 0;
}