#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];
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] == 0 && !visited[i][j]);
}
ll s = 0;
void dfs(ll i,ll j){
    r[s].push_back(p(i,j));
    visited[i][j] = 1;
    for(auto f : v){
        ll i1 = i+f.first,j1 = j+f.second;
        //cout << i1 << " ok " << j1 << endl;
        if(ok(i1,j1)){
            //cout << "idem" << endl;
            dfs(i1,j1);
        }
    }
}
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] = 0;
            }
            else if(s[j-1] == 'X'){
                mat[i][j] = 1;
            }
            else if(s[j-1] == 'A'){
                ai = i,aj = j;
                mat[i][j] = 0;
            }
            else{
                mat[i][j] = 0;
                bi = i,bj = j;
            }
        }
    }
    s = 0;
    dfs(ai,aj);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            visited[i][j] = 0;
        }
    }
    s = 1;
    dfs(bi,bj);
    if(m == 1){
        for(auto f : r[0]){
            if(f == p(bi,bj)){
                cout << 0 << endl;
                exit(0);
            }
        }
        /*for(auto f : r[0]){
            cout << f.first << " " << f.second << endl;
        }
        cout << endl;
        for(auto f : r[1]){
            cout << f.first << " " << f.second << endl;
        }
        cout << endl;*/
        ll sol = 1000000000;
        for(auto f : r[0]){
            ll dist = 1000000000;
            for(auto g : r[1]){
                dist = min(dist,max(abs(g.first-f.first-1),abs(g.second-f.second-1)));
            }
            sol = min(sol,dist);
        }
        cout << sol << endl;
        return 0;
    }
}
/*
6 1
A.XX..
..XX..
XXXX..
..XX..
..XX..
..XX.B
*/