#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];
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;

}
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);
}
void klir(){
    ff(i,1,n){
        ff(j,1,n){
            boja[i][j] = 0;
            pref[i][j][1] = pref[i][j][2] = 0;
        }
    }
}
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){
    ff(i,1,n){
        ff(j,1,n){
            if(mat[i][j] != 'X'){
                // 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];
                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 = 1;
    int r = n;
    while(l < r){
        int mid = (l + r) / 2;
        if(moze(mid)){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    cout << l << endl;
    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};
        }
    }
    if(m == 1){
        resi();
    }
    else{
        if(n <= 50){

        }
    }
    return 0;
}