#include <iostream>
#include <queue>
#include <vector>
#include <string>
#define MAKS (500)
#define MAKS2 (250000)
using namespace std;


//vector <string> mat[MAKS];
char mat[MAKS][MAKS];
int cntMine[MAKS][MAKS];
bool visited[MAKS][MAKS];
int n,m;
pair<int,int> A,B,C1,C,D;
void bfs()
{
    queue <pair<int,int> > kju;
    kju.push({A.first,A.second});
    visited[A.first][A.second]=true;
    pair<int,int> prvi=kju.front();
    kju.push({A.first+1,A.second});
    kju.push({A.first,A.second+1});
    kju.push({A.first-1,A.second});
    kju.push({A.first,A.second-1});
    cntMine[A.first][A.second]=0;
    kju.pop();
    int brojac=0;
    for(;!kju.empty();)
    {
        pair<int,int> drugi=kju.front();
        if(drugi.first-1>0 && !visited[drugi.first-1][drugi.second])
            kju.push({drugi.first-1,drugi.second});
        if(drugi.second-1>0 && !visited[drugi.first][drugi.second-1])
            kju.push({drugi.first,drugi.second-1});
        if(drugi.first+1<n && !visited[drugi.first+1][drugi.second])
            kju.push({drugi.first+1,drugi.second});
        if(drugi.second+1<n && !visited[drugi.first][drugi.second+1])
            kju.push({drugi.first,drugi.second+1});
        if(mat[drugi.first][drugi.second]=='X')
            brojac++;
        cntMine[drugi.first][drugi.second]=brojac;
        visited[drugi.first][drugi.second]++;
        kju.pop();
    }
}/*
int make_cntMine(int x,int y,int curr)
{
    if(visited[x][y])
    {
        if(cntMine[x][y]==-1)
            return MAKS*MAKS;
        return cntMine[x][y]=min(curr,cntMine[x][y]);
    }
        return MAKS*MAKS;
    visited[x][y]++;
    if(x<0 || y<0 || x>=n || y>=n)
        return MAKS*MAKS;
    if(x==0 && y==0)
    {
        return cntMine[0][0]=1*(mat[0][0]=='X');

    }
    return cntMine[x][y]=min(min(make_cntMine(x+1,y,cntMine[x+1][y]),make_cntMine(x,y+1)),min(make_cntMine(x-1,y),make_cntMine(x,y-1)))+(mat[x][y]=='X');
}
*/
void dfs1(int x,int y,int curr)
{
    if(x<0 || y<0 || x>=n || y>=n)
        return;
    if(mat[x][y]!='A')
    if(curr+(mat[x][y]=='X')>=cntMine[x][y])
        return;
    cntMine[x][y]=curr+(mat[x][y]=='X');
    curr=cntMine[x][y];
    if(curr==0)
    {
        C1.first=x;
        C1.second=y;
        if((x-B.first)*(x-B.first)+(y-B.second)*(y-B.second)<=(C.first-B.first)*(C.first-B.first)+(C.second-B.second)*(C.second-B.second))
            C=C1;
        //mat[x][y]='A';
    }
    dfs1(x+1,y,curr);
    dfs1(x-1,y,curr);
    dfs1(x,y+1,curr);
    dfs1(x,y-1,curr);
    return;
}
void dfs(int x,int y,int curr)
{
    if(x<0 || y<0 || x>=n || y>=n)
        return;
    if(mat[x][y]!='A')
    {
    if(cntMine[x][y]!=-1&&curr+1*(mat[x][y]=='X')>=cntMine[x][y])
        return;

    }
    cntMine[x][y]=curr+(mat[x][y]=='X');
    curr=cntMine[x][y];
    dfs(x+1,y,curr);
    dfs(x-1,y,curr);
    dfs(x,y+1,curr);
    dfs(x,y-1,curr);
    return;
}
void clearCnt()
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cntMine[i][j]=-1;
            return;
}
bool editMat(int k)
{
    int x;
    x=max(0,A.first-k);
    for(;x<=A.first+k;x++)
    {
        int y=min(A.second+k,n-1);
        if(mat[x][y]!='A' && mat[x][y]!='B')
        mat[x][y]='.';
    }
    x=max(0,A.first-k);
    for(;x<=A.first+k;x++)
    {
        int y=max(0,A.second-k);
        if(mat[x][y]!='A' && mat[x][y]!='B')
        mat[x][y]='.';
    }
    int y;
    y=max(0,A.second-k);
    for(;y<=A.first+k;y++)
    {
        int x=min(A.first+k,n-1);
        if(mat[x][y]!='A' && mat[x][y]!='B')
        mat[x][y]='.';
    }
    y=max(0,A.second-k);
    for(;y<=A.first+k;y++)
    {
        int x=max(0,A.first-k);
        if(mat[x][y]!='A' && mat[x][y]!='B')
            mat[x][y]='.';
    }
    dfs(A.first,A.second,0);

    if(cntMine[B.first][B.second]<=0)
        return 1;
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>mat[i][j];
            if(mat[i][j]=='A')
            {
                A.first=i;
                A.second=j;
            }
            if(mat[i][j]=='B')
            {
                B.first=i;
                B.second=j;
            }
            cntMine[i][j]=MAKS2;
        }
        //scanf("%s",&mat[i]);
    }
    C=A;D=A;

    //make_cntMine(B.first,B.second);
    //bfs();
    dfs1(A.first,A.second,0);
    A=C;
    mat[D.first][D.second]='.';
    mat[A.first][A.second]='A';
    if(cntMine[B.first][B.second]==0)
        cout<<-1;
    else
    {
        switch(m)
        {
        case 1:
            int k;
            for(k=1;!editMat(k);k++)clearCnt();
            cout<<k;
            break;
        case 2:
            break;
        }
    }

    return 0;
}