#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#define ull unsigned long long

using namespace std;

vector< pair<int,int> >Danilo,Drug;

ull N,M;
ull sx,sy,kx,ky;
ull mDxA,mDxB,mDyA,mDyB;
char S[1000][1000];
bool Da[1000][1000],
     Da2[1000][1000][1000],
     Dr[1000][1000];

bool ns=false,nk=false;

ull minD=1000000,minD2=10000000;

char accessA(int x,int y){
 if(x>=0 && x<N && y>=0 && y<N) return S[x][y];
 else return '0';
}
char accessB(int x,int y){
 if(x>=0 && x<N && y>=0 && y<N) return S[x][y];
 else return '0';
}

void pA(int x,int y){
 Da[x][y]=true;
 Danilo.push_back(make_pair(x,y));
 if(accessA(x-1,y)=='.')
    if(!Da[x-1][y]) pA(x-1,y);

 if(accessA(x,y-1)=='.')
    if(!Da[x][y-1]) pA(x,y-1);

 if(accessA(x+1,y)=='.')
    if(!Da[x+1][y]) pA(x+1,y);

 if(accessA(x,y+1)=='.')
    if(!Da[x][y+1]) pA(x,y+1);
}

void pAkX(int x,int y,int kX,int tX,int p){
 Da2[kX][x][y]=true;

 ull x1,x2,y1,y2;
         x1=x;
         y1=y;
         for(int j=0;j<Drug.size();j++)
         {
             x2=Drug[j].first;
             y2=Drug[j].second;

             ull Distance;
             Distance=max(abs(x1-x2),abs(y1-y2));

             //printf("(%llu,%llu) | (%llu,%llu) => %llu || kX=%d tX=%d ||\n",x1,y1,x2,y2,Distance,kX,tX);

             if(Distance==0 || Distance ==1){
                printf("%d",kX);
                exit(0);
             }

             if(Distance<p){
                    printf("%d",kX);
                    exit(0);
             }
         }

 if(accessA(x-1,y) =='.' || (tX<kX && accessA(x-1,y)!='0') )
  if(!Da2[kX][x-1][y])
    if(accessA(x-1,y)=='X') pAkX(x-1,y,kX,tX+1,p);
    else pAkX(x-1,y,kX,tX,p);

 if(accessA(x,y-1) =='.' || (tX<kX && accessA(x,y-1)!='0') )
  if(!Da2[kX][x][y-1])
    if(accessA(x,y-1)=='X') pAkX(x,y-1,kX,tX+1,p);
    else pAkX(x,y-1,kX,tX,p);

 if(accessA(x+1,y) =='.' || (tX<kX && accessA(x+1,y)!='0') )
 {
  if(!Da2[kX][x+1][y])
    if(accessA(x+1,y)=='X') pAkX(x+1,y,kX,tX+1,p);
    else pAkX(x+1,y,kX,tX,p);
 }
 if(accessA(x,y+1) =='.' || (tX<kX && accessA(x,y+1)!='0') )
  if(!Da2[kX][x][y+1])
    if(accessA(x,y+1)=='X') pAkX(x,y+1,kX,tX+1,p);
    else pAkX(x,y+1,kX,tX,p);
}

void pB(int x,int y){
 Dr[x][y]=true;
 Drug.push_back(make_pair(x,y));

 if(accessB(x-1,y)=='.')
    if(!Dr[x-1][y]) pB(x-1,y);

 if(accessB(x,y-1)=='.')
    if(!Dr[x][y-1]) pB(x,y-1);

 if(accessB(x+1,y)=='.')
    if(!Dr[x+1][y]) pB(x+1,y);

 if(accessB(x,y+1)=='.')
    if(!Dr[x][y+1]) pB(x,y+1);
}

int main()
{
    scanf("%llu%llu",&N,&M);
    getchar();
    for(int i=0;i<N;i++){
     gets(S[i]);
     if(!ns || !nk)
          for(int j=0;j<N;j++){
              if(S[i][j]=='A'){
                sx=i;
                sy=j;
              }
              if(S[i][j]=='B'){
                kx=i;
                ky=j;
              }
          }
    }
if(M==1)
{
    pA(sx,sy);
    pB(kx,ky);

    for(int i=0;i<Danilo.size();i++)
        for(int j=0;j<Drug.size();j++){
         ull x1,x2,y1,y2;
         x1=Danilo[i].first;
         y1=Danilo[i].second;
         x2=Drug[j].first;
         y2=Drug[j].second;

         ull Distance;
         Distance=max(abs(x1-x2),abs(y1-y2));

         if(Distance==0 || Distance==1){
          printf("0");
          return 0;
         }

         //printf("(%llu,%llu) | (%llu,%llu) => %llu\n",x1,y1,x2,y2,Distance);

         if(Distance<minD) {
          minD=Distance;
          minD2=min(abs(x1-x2),abs(y1-y2));
         }
         else if(Distance==minD)
                if(min(abs(x1-x2),abs(y1-y2))<minD2) minD2=min(abs(x1-x2),abs(y1-y2));

        }

     if(minD2<minD) printf("%d",minD-1);
     else printf("%d",minD);
}

else{
    pA(sx,sy);
    pB(kx,ky);

    for(int i=0;i<Danilo.size();i++)
        for(int j=0;j<Drug.size();j++){
         ull x1,x2,y1,y2;
         x1=Danilo[i].first;
         y1=Danilo[i].second;
         x2=Drug[j].first;
         y2=Drug[j].second;

         ull Distance;
         Distance=max(abs(x1-x2),abs(y1-y2));

         if(Distance==0 || Distance==1){
          printf("0");
          return 0;
         }

         //printf("(%llu,%llu) | (%llu,%llu) => %llu\n",x1,y1,x2,y2,Distance);

         if(Distance<minD) {
          mDxA=x1;
          mDxB=x2;
          mDyA=y1;
          mDyB=y2;
          minD=Distance;
          minD2=min(abs(x1-x2),abs(y1-y2));
         }

         else if(Distance==minD){
          if(min(abs(x1-x2),abs(y1-y2))<minD2){
           minD2=min(abs(x1-x2),abs(y1-y2));
           mDxA=x1;
           mDxB=x2;
           mDyA=y1;
           mDyB=y2;
          }
         }

        }

 ull p;
 if(minD%2==1)
    if(minD2<minD) p=minD/2;
    else p=minD/2+1;
 else p=minD/2;

 for(int moc=0;moc<=p;moc++){
  pAkX(sx,sy,moc,0,p);
 }
 printf("%llu",p);
}
    return 0;
}
/*
6 1
A.XX..
..XX..
XXXX..
..XX..
..XX..
..XX.B

7 2
AXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXB

7 2
AXXXXXX
.XXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXB

7 2
A.XXXXX
..XXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXB

5 2
AX...
XX...
.....
....B
.....



*/



/*
if(minD%2==0) if(minD2>minD) printf("%d",minD/2+1);
                   else printf("%d",minD/2);
     else if(minD2>minD) printf("%d",minD/2);
          else printf("%d",minD/2+1);
*/