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

struct Point{
    int x, y;
};

int n, m;
int mat[505][505];
bool visited[505][505];
bool visited1[505][505];
bool visited2[505][505];
#define MAXRANGE (251)

Point start;
Point finish;

void resVisi(bool w, bool w1, bool w2){
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(w){
                visited[i][j] = false;
            }
            if(w1){
                visited1[i][j] = false;
            }
            if(w2){
                visited2[i][j] = false;
            }
        }
    }
}

void explore(int x, int y){
    if(x < 0 || y < 0 || x >= n || y >= n || mat[x][y] == 1 || visited[x][y]){
        return;
    }

    visited[x][y] = true;

    explore(x + 1, y);
    explore(x - 1, y);
    explore(x, y + 1);
    explore(x, y - 1);
}

void explore(int x, int y, Point bomb, int k){
    int smalDFB = max(abs(bomb.x - x), abs(bomb.y - y));
    if(x < 0 || y < 0 || x >= n || y >= n || visited[x][y] || visited1[x][y] || (mat[x][y] == 1 && smalDFB > k)){
        return;
    }

    visited1[x][y] = true;

    explore(x + 1, y, bomb, k);
    explore(x - 1, y, bomb, k);
    explore(x, y + 1, bomb, k);
    explore(x, y - 1, bomb, k);
}

void explore(int x, int y, Point bomb1, Point bomb2, int k){
    int smalDFB1 = max(abs(bomb1.x - x), abs(bomb1.y - y));
    int smalDFB2 = max(abs(bomb2.x - x), abs(bomb2.y - y));
    if(x < 0 || y < 0 || x >= n || y >= n || visited[x][y] || visited2[x][y] || (mat[x][y] == 1 && smalDFB1 > k && smalDFB2 > k)){
        return;
    }

    visited2[x][y] = true;

    explore(x + 1, y, bomb1, bomb2, k);
    explore(x - 1, y, bomb1, bomb2, k);
    explore(x, y + 1, bomb1, bomb2, k);
    explore(x, y - 1, bomb1, bomb2, k);
}

bool canMine(int k, Point bomb){
    visited[bomb.x][bomb.y] = false;
    explore(bomb.x, bomb.y, bomb, k);

    if(visited1[finish.x][finish.y]){
        return true;
    }

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(i == bomb.x && j == bomb.y){
                continue;
            }
            if(!visited1[i][j] && !visited[i][j]){
                continue;
            }
            if(mat[i + 1][j] == 1 || mat[i - 1][j] == 1 || mat[i][j + 1] == 1 || mat[i][j - 1] == 1){
                bool wz = visited[i][j];
                bool wz1 = visited1[i][j];
                visited[i][j] = false;
                visited1[i][j] = false;
                explore(i, j, bomb, Point{i, j}, k);
                if(visited2[finish.x][finish.y]){
                    return true;
                }
                for(int i1 = max(0, i - k); i1 < min(n, i + k + 1); ++i1){
                    for(int j1 = max(0, j - k); j1 < min(n, j + k + 1); ++j1){
                        visited2[i1][j1] = false;
                    }
                }
                visited[i][j] = wz;
                visited1[i][j] = wz1;
            }
        }
    }

    for(int i1 = max(0, bomb.x - k); i1 < min(n, bomb.x + k + 1); ++i1){
        for(int j1 = max(0, bomb.y - k); j1 < min(n, bomb.y + k + 1); ++j1){
            visited1[i1][j1] = false;
        }
    }
    visited[bomb.x][bomb.y] = true;
    return false;
}


bool canMine(int k){
    resVisi(true, true, true);
    explore(start.x, start.y);
    if(visited[finish.x][finish.y]){
        return true;
    }

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(!visited[i][j]){
                continue;
            }
            if(mat[i + 1][j] == 1 || mat[i - 1][j] == 1 || mat[i][j + 1] == 1 || mat[i][j - 1] == 1){
                if(m == 1){
                    visited[i][j] = false;
                    explore(i, j, Point{i, j}, k);
                    if(visited1[finish.x][finish.y]){
                        return true;
                    }
                    for(int i1 = max(0, i - k); i1 < min(n, i + k + 1); ++i1){
                        for(int j1 = max(0, j - k); j1 < min(n, j + k + 1); ++j1){
                            visited1[i1][j1] = false;
                        }
                    }
                    visited[i][j] = true;
                }else{
                    bool x = canMine(k, Point{i, j});
                    if(x){
                        return true;
                    }
                }
            }
        }
    }

    return false;
}

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){
            char c;
            cin >> c;
            if(c == '.'){
                mat[i][j] = 0;
            }else if(c == 'X'){
                mat[i][j] = 1;
            }else if(c == 'A'){
                mat[i][j] = 2;
                start = Point{i, j};
            }else if(c == 'B'){
                mat[i][j] = 3;
                finish = Point{i, j};
            }
        }
    }

    int l = 0;
    int r = MAXRANGE;
    int mid;
    int wrks = 250;

    while(l <= r){
        mid = (l + r) / 2;
        bool w1 = canMine(mid);
        if(w1){
            wrks = mid;
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }

    cout << wrks << "\n";
    return 0;
}


//#include <bits/stdc++.h>
//using namespace std;
//
//struct Point{
//    int x, y;
//};
//
//int n, m;
//int mat[505][505];
//bool visited[505][505];
//bool visited1[505][505];
//bool visited2[505][505];
//#define MAXRANGE (251)
//
//Point start;
//Point finish;
//
//void resVisi(bool w, bool w1, bool w2){
//    for(int i = 0; i < n; ++i){
//        for(int j = 0; j < n; ++j){
//            if(w){
//                visited[i][j] = false;
//            }
//            if(w1){
//                visited1[i][j] = false;
//            }
//            if(w2){
//                visited2[i][j] = false;
//            }
//        }
//    }
//}
//
//void explore(int x, int y){
//    if(x < 0 || y < 0 || x >= n || y >= n || mat[x][y] == 1 || visited[x][y]){
//        return;
//    }
//
//    visited[x][y] = true;
//
//    explore(x + 1, y);
//    explore(x - 1, y);
//    explore(x, y + 1);
//    explore(x, y - 1);
//}
//
//void explore(int x, int y, Point bomb, int k){
//    int smalDFB = max(abs(bomb.x - x), abs(bomb.y - y));
//    if(x < 0 || y < 0 || x >= n || y >= n || visited[x][y] || visited1[x][y] || (mat[x][y] == 1 && smalDFB > k)){
//        return;
//    }
//
//    visited1[x][y] = true;
//
//    explore(x + 1, y, bomb, k);
//    explore(x - 1, y, bomb, k);
//    explore(x, y + 1, bomb, k);
//    explore(x, y - 1, bomb, k);
//}
//
//void explore(int x, int y, Point bomb1, Point bomb2, int k){
//    int smalDFB1 = max(abs(bomb1.x - x), abs(bomb1.y - y));
//    int smalDFB2 = max(abs(bomb2.x - x), abs(bomb2.y - y));
//    if(x < 0 || y < 0 || x >= n || y >= n || visited[x][y] || visited2[x][y] || (mat[x][y] == 1 && smalDFB1 > k && smalDFB2 > k)){
//        return;
//    }
//
//    visited2[x][y] = true;
//
//    explore(x + 1, y, bomb1, bomb2, k);
//    explore(x - 1, y, bomb1, bomb2, k);
//    explore(x, y + 1, bomb1, bomb2, k);
//    explore(x, y - 1, bomb1, bomb2, k);
//}
//
//bool canMine(int k, Point bomb){
//    visited[bomb.x][bomb.y] = false;
//    explore(bomb.x, bomb.y, bomb, k);
//
//    if(visited1[finish.x][finish.y]){
//        return true;
//    }
//
//    for(int i = 0; i < n; ++i){
//        for(int j = 0; j < n; ++j){
//            if(i == bomb.x && j == bomb.y){
//                continue;
//            }
//            if(!visited1[i][j] && !visited[i][j]){
//                continue;
//            }
//            if(mat[i + 1][j] == 1 || mat[i - 1][j] == 1 || mat[i][j + 1] == 1 || mat[i][j - 1] == 1){
//                bool wz = visited[i][j];
//                bool wz1 = visited1[i][j];
//                visited[i][j] = false;
//                visited1[i][j] = false;
//                explore(i, j, bomb, Point{i, j}, k);
//                if(visited2[finish.x][finish.y]){
//                    return true;
//                }
//                for(int i1 = max(0, i - k); i1 < min(n, i + k + 1); ++i1){
//                    for(int j1 = max(0, j - k); j1 < min(n, j + k + 1); ++j1){
//                        visited2[i1][j1] = false;
//                    }
//                }
//                visited[i][j] = wz;
//                visited1[i][j] = wz1;
//            }
//        }
//    }
//
//    visited[bomb.x][bomb.y] = true;
//    return false;
//}
//
//
//bool canMine(int k){
//    resVisi(true, true, true);
//    explore(start.x, start.y);
//    if(visited[finish.x][finish.y]){
//        return true;
//    }
//
//    for(int i = 0; i < n; ++i){
//        for(int j = 0; j < n; ++j){
//            if(!visited[i][j]){
//                continue;
//            }
//            if(mat[i + 1][j] == 1 || mat[i - 1][j] == 1 || mat[i][j + 1] == 1 || mat[i][j - 1] == 1){
//                if(m == 1){
//                    visited[i][j] = false;
//                    explore(i, j, Point{i, j}, k);
//                    if(visited1[finish.x][finish.y]){
//                        return true;
//                    }
//                    for(int i1 = max(0, i - k); i1 < min(n, i + k + 1); ++i1){
//                        for(int j1 = max(0, j - k); j1 < min(n, j + k + 1); ++j1){
//                            visited1[i1][j1] = false;
//                        }
//                    }
//                    visited[i][j] = true;
//                }else{
//                    bool x = canMine(k, Point{i, j});
//                    if(x){
//                        return true;
//                    }
//                }
//            }
//        }
//    }
//
//    return false;
//}
//
//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){
//            char c;
//            cin >> c;
//            if(c == '.'){
//                mat[i][j] = 0;
//            }else if(c == 'X'){
//                mat[i][j] = 1;
//            }else if(c == 'A'){
//                mat[i][j] = 2;
//                start = Point{i, j};
//            }else if(c == 'B'){
//                mat[i][j] = 3;
//                finish = Point{i, j};
//            }
//        }
//    }
//
//    int l = 0;
//    int r = MAXRANGE;
//    int mid;
//    int wrks = 250;
//
//    while(l <= r){
//        mid = (l + r) / 2;
//        bool w1 = canMine(mid);
//        if(w1){
//            wrks = mid;
//            r = mid - 1;
//        }else{
//            l = mid + 1;
//        }
//    }
//
//    cout << wrks << "\n";
//    return 0;
//}