#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define xx first
#define yy second
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
int n,m;
bool dobar[505][505];
char mat[505][505];
bool check(int x, int y){
    if(x <= 0 || x > n)return 0;
    if(y <= 0 || y > n)return 0;
    if(mat[x][y] == 'X')return 0;
    if(dobar[x][y])return 0;
    return 1;
}
pii a,b;
void dfs1(int x, int y){
    if(dobar[x][y])return;
    dobar[x][y] = 1;
    if(check(x,y+1))dfs1(x,y+1);
    if(check(x+1,y))dfs1(x+1,y);
    if(check(x-1,y))dfs1(x-1,y);
    if(check(x,y-1))dfs1(x,y-1);
    return;
}
struct polje{
    int x;
    int y;
    int dis;
};
bool f[505][505];
queue<polje>q;
bool bio[505][505];
int ud[505][505][4];
bool check2(int x, int y){
    if(x <= 0 || x > n)return 0;
    if(y <= 0 || y > n)return 0;
    if(bio[x][y])return 0;
    return 1;
}
void bfs(int ind){
    while(!q.empty()){
        polje pom = q.front();
        q.pop();
        bio[pom.x][pom.y] = 1;
        if(ud[pom.x][pom.y][ind] == -1)
            ud[pom.x][pom.y][ind] = pom.dis;
        else
            ud[pom.x][pom.y][ind] = min(pom.dis, ud[pom.x][pom.y][ind]);
        int x = pom.x;
        int y = pom.y;
        int val = pom.dis;
        if(!f[x][y]){

            ff(i,-1,1){
                ff(j,-1,1){
                    if(i == 0 && j == 0)continue;
                        if(check2(x+i,y+j)){
                            bio[x+i][y+j] = 1;
                            q.push({x+i,y+j,val+1});
                        }
                    }
            }
            continue;
        }
        if(check2(x,y+1)){
            bio[x][y+1] = 1;
            q.push({x,y+1,val});
        }
        if(check2(x+1,y)){
            bio[x+1][y] = 1;
            q.push({x+1,y,val});
        }
        if(check2(x-1,y)){
            bio[x-1][y] = 1;
            q.push({x-1,y,val});
        }
        if(check2(x,y-1)){
            bio[x][y - 1] = 1;
            q.push({x,y-1,val});
        }


    }
}
bool bio2[505][505];
bool check3(int x, int y){
    if(x <= 0 || x > n)return 0;
    if(y <= 0 || y > n)return 0;
    if(mat[x][y] == 'X')return 0;
    if(bio2[x][y])return 0;
    return 1;
}
void dfs(int x, int y){
    if(bio2[x][y])return;
    bio2[x][y] = 1;
    f[x][y] = 1;
    q.push({x,y,0});
    if(check3(x,y+1))dfs(x,y+1);
    if(check3(x+1,y))dfs(x+1,y);
    if(check3(x-1,y))dfs(x-1,y);
    if(check3(x,y-1))dfs(x,y-1);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    ff(i,1,n){
        string x;
        cin >> x;
        ff(j,1,n){
            mat[i][j] = x[j - 1];
            if(mat[i][j] == 'A')a = {i,j};
            else if(mat[i][j] == 'B')b = {i,j};
            ud[i][j][1] = ud[i][j][2] = -1;
        }
    }
    dfs1(a.xx,a.yy);
    if(dobar[b.xx][b.yy]){
        cout << -1;
        return 0;
    }
    ff(i,1,n){
        ff(j,1,n){
            if(dobar[i][j]){
                q.push({i,j,0});
                //f[i][j] = 1;
                //cout << 1 << " ";
            }
        }
        //cout << endl;

    }
    bfs(1);
    while(!q.empty())q.pop();
    ff(i,1,n){
        ff(j,1,n){
            bio[i][j] = 0;
        }
    }
    dfs(b.xx,b.yy);
    bfs(2);
    int res = 1e9;
    int res2 = 1e9;
    ff(i,1,n){
        ff(j,1,n){
            ud[i][j][0] = max(ud[i][j][1], ud[i][j][2]-1);
            //cout << ud[i][j][1] << " ";
            res = min(res, ud[i][j][0]);
            if(dobar[i][j])res2 = min(res2, ud[i][j][0]);
        }
        //cout << endl;
    }
    if(m == 1)cout << res2 << endl;
    else cout << res << endl;
    return 0;
}