#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll,ll> p;
const ll N = 505;

bool visited[N][N];
ll mat[N][N],comp[N][N];
bool moze0[N][N],moze1[N][N];
vector <p> v,r[2];
ll n,m;

bool ok(ll i,ll j){
    return (1 <= i && 1 <= j && i <= n && j <= n && mat[i][j] == 1 && !visited[i][j]);
}
ll s = 0;
void dfs(ll i,ll j){
    r[s].push_back(p(i,j));
    if(s == 0){
        moze0[i][j] = 1;
    }
    else{
        moze1[i][j] = 1;
    }
    comp[i][j] = s;
    visited[i][j] = 1;
    for(auto f : v){
        ll i1 = i+f.first,j1 = j+f.second;
        if(ok(i1,j1)){
            dfs(i1,j1);
        }
    }
}
ll najm(ll i1,ll j1,ll i2,ll j2){
    if(i1 < i2){
        if(j1 < j2){
            if(mat[i2][j2-1] == 2 && mat[i2-1][j2] == 2){
                return max(abs(j2-j1),abs(i2-i1));
            }
            else{
                return max(abs(j2-j1)-1,abs(i2-i1)-1);
            }
        }
        else{
            if(mat[i2][j2+1] == 2 && mat[i2-1][j2] == 2){
                return max(abs(j2-j1),abs(i2-i1));
            }
            else{
                return max(abs(j2-j1)-1,abs(i2-i1)-1);
            }
        }
    }
    else{
        if(j1 < j2){
            if(mat[i2][j2-1] == 2 && mat[i2+1][j2] == 2){
                return max(abs(j2-j1),abs(i2-i1));
            }
            else{
                return max(abs(j2-j1)-1,abs(i2-i1)-1);
            }
        }
        else{
            if(mat[i2][j2+1] == 2 && mat[i2+1][j2] == 2){
                return max(abs(j2-j1),abs(i2-i1));
            }
            else{
                return max(abs(j2-j1)-1,abs(i2-i1)-1);
            }
        }
    }
}
ll jednabomba(){
    ll sol = 1000000000;
    for(auto f : r[0]){
        ll dist = 1000000000;
        ll i1 = f.first,j1 = f.second;
        for(auto g : r[1]){
            ll i2 = g.first,j2 = g.second;
            if(f.first == g.first){
                dist = min(dist,abs(g.second-f.second)-1);
            }
            else if(f.second == g.second){
                dist = min(dist,abs(f.first-g.first)-1);
            }
            else{
                dist = min(dist,najm(i1,j1,i2,j2));
            }
        }
        sol = min(sol,dist);
    }
    return sol;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    v.push_back(p(0,1));
    v.push_back(p(0,-1));
    v.push_back(p(1,0));
    v.push_back(p(-1,0));
    cin >> n >> m;
    ll ai = 0,aj = 0,bi = 0,bj = 0;
    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;
        for(int j = 1; j <= n; j++){
            if(s[j-1] == '.'){
                mat[i][j] = 1;
            }
            else if(s[j-1] == 'X'){
                mat[i][j] = 2;
            }
            else if(s[j-1] == 'A'){
                ai = i,aj = j;
                mat[i][j] = 1;
            }
            else{
                mat[i][j] = 1;
                bi = i,bj = j;
            }
        }
    }
    s = 0;
    dfs(ai,aj);
    if(visited[bi][bj]){
        cout << "-1" << endl;
        return 0;
    }
    s = 1;
    dfs(bi,bj);
    ll m1 = jednabomba();
    if(m == 1){
        cout << m1 << endl;
        return 0;
    }
    /// m = 2
    ll sol = m1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            ll dist = 1000000000;
            for(auto g : r[1]){
                ll i2 = g.first,j2 = g.second;
                if(i == i2){
                    dist = min(dist,abs(j2-j)-1);
                }
                else if(j == j2){
                    dist = min(dist,abs(i-i2)-1);
                }
                else{
                    dist = min(dist,najm(i,j,i2,j2));
                }
            }
            ll pre = 1000000000;
            if(mat[i][j] == 2){
                for(auto f : r[0]){
                    ll i2 = f.first,j2 = f.second;
                    if(i == i2){
                        pre = min(pre,abs(j2-j));
                    }
                    else if(j == j2){
                        pre = min(pre,abs(i-i2));
                    }
                    else{
                        pre = min(pre,max(abs(i-i2),abs(j-j2)));
                    }
                }
            }
            else{
                for(auto f : r[0]){
                    ll i2 = f.first,j2 = f.second;
                    if(i == i2){
                        pre = min(pre,max(0ll,abs(j2-j)-1));
                    }
                    else if(j == j2){
                        pre = min(pre,max(0ll,abs(i-i2)-1));
                    }
                    else{
                        pre = min(pre,najm(i2,j2,i,j));
                    }
                }
            }
            //cout << i << " " << j << " " << dist << " " << pre << endl;
            sol = min(sol,max(dist,pre));
        }
    }
    cout << sol << endl;
}
/*
6 1
A.XX..
..XX..
XXXX..
..XX..
..XX..
..XX.B
6 1
AX....
X.X...
..X...
...X..
....XX
....XB
7 2
AXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXB
6 2
A.XXXX
..XXXX
XXXXXX
..XXXX
..XXXX
..XXXB

*/