#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define xx first
#define yy second
using namespace std;
typedef pair<int,int>pii;
int n,m;
char mat[505][505];
int boja[505][505];
int pref[505][505][3];
int pommat[505][505];
bool dobar[505][505];
pii a;
pii b;
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(boja[x][y] != 0)return 0;
    return 1;

}
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(dobar[x][y])return 0;
    return 1;
}
void dfs(int x, int y, int col){
    if(boja[x][y] != 0)return;
    boja[x][y] = col;
    if(check(x,y+1))dfs(x,y+1,col);
    if(check(x+1,y))dfs(x+1,y,col);
    if(check(x,y-1))dfs(x,y-1,col);
    if(check(x-1,y))dfs(x-1,y,col);
}
bool check2(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(boja[x][y] == 0)return 0;
    return 1;
}
void klir(){
    ff(i,1,n){
        ff(j,1,n){
            boja[i][j] = 0;
            pref[i][j][1] = pref[i][j][2] = 0;
           // mat[i][j] = pommat[i][j];
        }
    }
}
void precalc(){
    ff(i,1,n){
        ff(j,1,n){
            ff(k,1,2)pref[i][j][k] = pref[i-1][j][k] + pref[i][j-1][k] - pref[i-1][j-1][k];
            if(boja[i][j] == 1 || boja[i][j] == 2)pref[i][j][boja[i][j]]++;
        }
    }
}
bool moze(int x){
    //cout << x << endl;
    ff(i,1,n){
        ff(j,1,n){
            if(mat[i][j] != 'X' && boja[i][j] == 1){
                // gornji levi
                pii dd = {min(i+x+1,n),min(j+x+1,n)};
                pii gl = {max(1,i-x-1),max(1,j-x-1)};
                int aovi = pref[dd.xx][dd.yy][1] - pref[dd.xx][gl.yy-1][1] - pref[gl.xx - 1][dd.yy][1] + pref[gl.xx-1][gl.yy-1][1];
                int bovi = pref[dd.xx][dd.yy][2] - pref[dd.xx][gl.yy-1][2] - pref[gl.xx - 1][dd.yy][2] + pref[gl.xx-1][gl.yy-1][2];
                dd = {i+x+1,j+x+1};
                gl = {i-x-1,j-x-1};
                if(x == 0 && i == 2 && j == 1){
                    cout << dd.xx << " " << dd.yy << endl << gl.xx << " " << gl.yy << endl;
                }
                if(check2(dd.xx,dd.yy)){
                    if(boja[dd.xx][dd.yy] == 1)aovi--;
                    else bovi--;
                }
                if(check2(dd.xx,gl.yy)){
                    if(boja[dd.xx][gl.yy] == 1)aovi--;
                    else bovi--;
                }
                if(check2(gl.xx,gl.yy)){
                    if(boja[gl.xx][gl.yy] == 1)aovi--;
                    else bovi--;
                }
                if(check2(gl.xx,dd.yy)){
                    if(boja[gl.xx][dd.yy] == 1)aovi--;
                    else bovi--;
                }
                if(aovi * bovi > 0)return 1;
            }
        }
    }
    return 0;
}
void resi(){
    klir();
    dfs(a.xx, a.yy, 1);
    if(boja[b.xx][b.yy] == 1){
        cout << -1;
        exit(0);
    }
    dfs(b.xx,b.yy, 2);
    precalc();
    int l = 0;
    int r = n;
    while(l < r){
       // cout << l << " " << r << endl;
        int mid = (l + r) / 2;
        if(moze(mid)){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    cout << l << endl;
    return;
}
void dfs1(int x, int y){
    if(dobar[x][y])return;
    dobar[x][y] = 1;
    if(check3(x-1,y))dfs1(x-1,y);
    if(check3(x,y-1))dfs1(x,y-1);
    if(check3(x+1,y))dfs1(x+1,y);
    if(check3(x,y+1))dfs1(x,y+1);

}
bool probaj(int x, int y, int val){
    ff(i,1,n){
        ff(j,1,n){
            mat[i][j] = pommat[i][j];
        }
    }
    int levox = max(x-val,1);
    int desnox = min(x+val,n);
    int levoy = max(y-val,1);
    int desnoy = min(y+val,n);
    ff(i,levox,desnox){
        ff(j,levoy,desnoy){
            if(mat[i][j] == 'X')mat[i][j] = '.';
        }
    }
   // cout << x << " " << y << endl;
    klir();
    dfs(a.xx, a.yy, 1);
    if(boja[b.xx][b.yy] == 1){
        return 1;
    }
   /* cout << x <<  " " << y << "  " << val << endl;
    ff(i,1,n){
        ff(j,1,n){
            cout << mat[i][j];
        }
        cout << endl;
    }
    cout << endl << endl;*/
    dfs(b.xx,b.yy, 2);
    precalc();
    return moze(val);
}
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};
            pommat[i][j] = mat[i][j];
        }
    }
    dfs1(a.xx,a.yy);
    if(dobar[b.xx][b.yy]){
        cout <<-1;
        return 0;
    }
    if(m == 1){
        resi();
        return 0;
    }
    else{
        if(1){
            int minsol = 1e9;
            ff(i,1,n){
                ff(j,1,n){
                    //klir();
                    //dfs(a.xx,a.yy,1);
                    int l = 1;
                    int r = n;
                    if(!dobar[i][j])continue;
                    while(l < r){
                        int mid = (l+r)/2;
                        if(probaj(i,j,mid)){
                            r = mid;
                        }else l = mid+1;
                    }
                    minsol = min(minsol, l);
                }
            }
            cout << minsol << endl;
            return 0;
        }
    }
    return 0;
}