#include<bits/stdc++.h>
using namespace std;

const int maxN = 510;

struct polje {int i; int j;};
int n, k;
char mat[maxN][maxN];
char pom[maxN][maxN];
bool pos[maxN][maxN];
vector<polje> regijeOne, regijeTwo,
              regijeThree, regijeFour;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int iA, jA, iB, jB;

void pretvoriMat(int ip, int jp, int p) {
    for(int i = max(0, ip - p); i <= min(n - 1, ip + p); ++i)
        for(int j = max(0, jp - p); j <= min(n - 1, jp + p); ++j)
            if(mat[i][j] != 'A' && mat[i][j] != 'B')
                mat[i][j] = '.';

}
void vratiIzPomUMat() {
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            mat[i][j] = pom[i][j];
}
void vratiPosNaFalse() {
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            pos[i][j] = false;
}
bool nasao;
void dfsRegije(int i, int j, const int& x) {
    if(x == 1 && mat[i][j] == 'B') {
        cout << -1;
        exit(0);
    }
    if(x == 3 && mat[i][j] == 'B')
        nasao = true;
    if(i < 0 || i >= n ||
       j < 0 || j >= n ||
       mat[i][j] == 'X')
        return;
    if(pos[i][j])
        return;
    if(x == 1)
        regijeOne.push_back({i, j});
    else if(x == 2)
        regijeTwo.push_back({i, j});
    else if(x == 3)
        regijeThree.push_back({i, j});
    else
        regijeFour.push_back({i, j});
    pos[i][j] = true;

    for(int pr = 0; pr < 4; ++pr)
        dfsRegije(i + dx[pr], j + dy[pr], x);
}
int aps(int a, int b) {
    if(a > b)
        return a - b;
    return b - a;
}
int maximus(int a, int b) {
    if(a == b)
        return a;
    return max(a, b) - 1;
}
bool jeste;
int minOverall, minTren;
bool bppr(int l, int d) {
    int mid = l + (d - l) / 2;
    for(int T = 0; T < regijeOne.size(); ++T) {
        pretvoriMat(regijeOne[T].i, regijeOne[T].j, mid);
        vratiPosNaFalse();
        dfsRegije(regijeOne[T].i, regijeOne[T].j, 3);
        dfsRegije(iB, jB, 4);
        if(nasao) {
            jeste = true;
            minOverall = min(minOverall, mid);
        }
        else {
            for(int i = 0; i < regijeThree.size(); ++i) {
                for(int j = 0; j < regijeFour.size(); ++j) {
                    minTren = min(minTren, maximus(aps(regijeThree[i].i, regijeFour[j].i), aps(regijeThree[i].j, regijeFour[j].j)));
                }
                if(minTren <= mid) {
                    minOverall = min(minTren, minOverall);
                    jeste = true;
                    break;
                }
            }
        }
        regijeThree.clear();
        regijeFour.clear();
        vratiIzPomUMat();
        if(jeste)
            break;
    }
    if(jeste)
        return true;
    minTren = 2e4;
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> k;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j) {
            cin >> mat[i][j];
            if(mat[i][j] == 'A')
            {iA = i, jA = j;}
            if(mat[i][j] == 'B')
            {iB = i, jB = j;}
        }

    dfsRegije(iA, jA, 1);
    dfsRegije(iB, jB, 2);

    if(k == 1) {
        minOverall = minTren = 2e4;
        for(int i = 0; i < regijeOne.size(); ++i) {
            for(int j = 0; j < regijeTwo.size(); ++j) {
                minTren = min(minTren, maximus(aps(regijeOne[i].i, regijeTwo[j].i), aps(regijeOne[i].j, regijeTwo[j].j)));
            }
            minOverall = min(minTren, minOverall);
        }
        cout << minOverall;
    }
    else {
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                pom[i][j] = mat[i][j];
        minOverall = minTren = 2e4;
        int l = 1, d = n - 1;
        while(l <= d) {
            minTren = 2e4;
            jeste = false;
            if(bppr(l, d))
                d = l + (d - l) / 2 - 1;
            else
                l = l + (d - l) / 2 + 1;
        }
        cout << minOverall;
    }
    return 0;
}
/*
6 1
A.XX..
..XX..
XXXX..
..XX..
..XX..
..XX.B
*/
/*
7 2
AXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXB
*/