#include <bits/stdc++.h>

#define ll long long
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define mod 1000000007

using namespace std;

int n,m;
pair<int,int>a,b;
char c[510][510];
bool ch[510][510],moze[510][510];
vector<pair<int,int>>f,g,h;

void check_zero(int i,int j){
    if (i<1 or i>n or j<1 or j>n)return;
    if (ch[i][j] or c[i][j]=='X')return;
    ch[i][j]=true;
    f.pb({i,j});
    check_zero(i+1,j),check_zero(i,j+1),check_zero(i-1,j),check_zero(i,j-1);
}

void oboji(int i,int j){
    if (i<1 or i>n or j<1 or j>n)return;
    if (moze[i][j] or c[i][j]=='X')return;
    moze[i][j]=true;
    g.pb({i,j});
    oboji(i+1,j),oboji(i,j+1),oboji(i-1,j),oboji(i,j-1);
}

int calc(pair<int,int>i,pair<int,int>j){
    if (i.fi<1 or i.se<1 or i.fi>n or i.se>n)return 1e9;
    int pr1=abs(i.fi-j.fi),pr2=abs(i.se-j.se);
    int ok=max(pr1,pr2)-1;
    if (pr1==pr2)ok++;
    return ok;
}

int calc2(pair<int,int>i,pair<int,int>j){
    if (i.fi<1 or i.se<1 or i.fi>n or i.se>n)return 1e9;
    int pr1=abs(i.fi-j.fi),pr2=abs(i.se-j.se);
    int ok=max(pr1,pr2)-1;
    if (pr1==pr2 or c[i.fi][i.se]=='X')ok++;
    return ok;
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            cin>>c[i][j];
            if (c[i][j]=='A')a={i,j};
            if (c[i][j]=='B')b={i,j};
        }
    }
    check_zero(a.fi,a.se);
    oboji(b.fi,b.se);
    if (ch[b.fi][b.se])return cout<<-1,0;

    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (ch[i][j] or moze[i][j])continue;
            h.pb({i,j});
        }
    }

    int answer=1e9;
    for (auto i:f){
        for (auto j:g){
            //pr1 za visinu, pr2 za duzinu
            int pr1=abs(i.fi-j.fi),pr2=abs(i.se-j.se);
            int ok=max(pr1,pr2)-1;
            if (pr1==pr2)ok++;

            answer=min(answer,ok);
        }
    }
    if (m==1)return cout<<answer,0;

    for (auto i:h){
        int lol,lol1=1e9,lol2=1e9,lol3=1e9,lol4=1e9;
        for (auto j:g){
            lol1=min({lol1,
                     calc({i.fi-1,i.se},j),
                     calc({i.fi+1,i.se},j),
                     calc({i.fi,i.se-1},j),
                     calc({i.fi,i.se+1},j)});
            lol2=min(lol2,calc2(i,j));
        }
        for (auto j:f){
            lol3=min({lol3,
                     calc({i.fi-1,i.se},j),
                     calc({i.fi+1,i.se},j),
                     calc({i.fi,i.se-1},j),
                     calc({i.fi,i.se+1},j)});
            lol4=min(lol4,calc2(i,j));
        }

        lol=min(max(lol1,lol4),max(lol2,lol3));
        answer=min(answer,lol);
    }
    cout<<answer;
    return 0;
}

/*
za -1

7 9
X.X.XBX
XX.XX.X
XXX....
A.X....
X..XXX.
X.XXXX.
.......

6 1
A.XX..
..XX..
XXXX..
..XX..
..XX..
..XX.B

6 1
A.XX..
.XXX..
XXXX..
..XX..
..XX..
..XX.B

7 2
AXXXXXX
XXXXXXX
XXXXXXX
XXX.XXX
XXXXXXX
XXXXXXX
XXXXXXB

4 1
BXXA
X.X.
X.X.
....
*/