#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
/*
A = -1
B = -2
. = -3
X = -4
*/
int n;
std::vector<std::vector<int>> ogMatrica;
struct pozicija
{
	int i,j;
};

int NadjiPraviMin(int niz[4])
{
	int trMin = std::numeric_limits<int>::max();
	for(int i = 0; i < 4; i++)
	{
		if(niz[i] >= 0)
		{
			trMin = std::min(trMin,niz[i]);
		}
	}
	return trMin;
}
void srediPoziciju(std::vector<std::vector<int>>* mat,pozicija p,int k)
{

	int iPocetno = std::max(0,p.i - k/2 - 1);
	int jPocetno = std::max(0,p.j - k/2 - 1);
	int iKrajnje = std::min(iPocetno + 2*k+1,n+2);
	int jKrajnje = std::min(jPocetno + 2*k+1,n+2);
	for(int i = iPocetno; i < iKrajnje;i++)
	{
		for(int j = jPocetno; j < jKrajnje;j++)
		{
			if((*mat).at(i).at(j) == -4)
			{
				(*mat).at(i).at(j) = (*mat).at(p.i).at(p.j)+1;
			}
			else if((*mat).at(i).at(j) >= 0)
			{
				(*mat).at(i).at(j) = std::min((*mat).at(p.i).at(p.j)+1,(*mat).at(i).at(j));
			}
		}
	}
	
}

int BFSbombe(int k,std::vector<std::vector<int>> mat,int i,int j,int n)
{
	std::list<pozicija> red;
	pozicija poz; poz.i=i; poz.j = j;
	red.push_back(poz);
	mat[i][j] = 0;
	while(true)
	{
		pozicija trPoz = *red.begin();
		if(mat[trPoz.i][trPoz.j] == -2)
		{
			int niz[] = {mat[trPoz.i+1][trPoz.j],mat[trPoz.i][trPoz.j+1],mat[trPoz.i-1][trPoz.j],mat[trPoz.i][trPoz.j-1]};
			return NadjiPraviMin(niz);
		}
		if(mat[trPoz.i][trPoz.j] == -3)
		{
			int niz[] = {mat[trPoz.i+1][trPoz.j],mat[trPoz.i][trPoz.j+1],mat[trPoz.i-1][trPoz.j],mat[trPoz.i][trPoz.j-1]};
			mat[trPoz.i][trPoz.j] = NadjiPraviMin(niz);
		}
		
		if(j > 1)
		{
			pozicija p; p.i = trPoz.i;  p.j = trPoz.j-1;
			if(mat[p.i][p.j] == -4)
			{
				srediPoziciju(&mat,trPoz,k);
			}
			red.push_back(p);
		}
		if(i > 1)
		{
			pozicija p; p.i = trPoz.i-1;  p.j = trPoz.j;
			if(mat[p.i][p.j] == -4)
			{
				srediPoziciju(&mat,trPoz,k);
			}
			red.push_back(p);
		}
		if(trPoz.i < n)
		{
			pozicija p; p.i = trPoz.i+1;  p.j = trPoz.j;
			if(mat[p.i][p.j] == -4)
			{
				srediPoziciju(&mat,trPoz,k);
			}
			red.push_back(p);
		}
		if(trPoz.j < n)
		{
			pozicija p; p.i = trPoz.i;  p.j = trPoz.j+1;
			if(mat[p.i][p.j] == -4)
			{
				srediPoziciju(&mat,trPoz,k);
			}
			red.push_back(p);
		}
		red.pop_front();
	}
	return 0;
}


int main()
{
	int brBombi;
	scanf("%d %d",&n,&brBombi);
	int maxK = std::ceil(n/2.0);
	ogMatrica.resize(n+2);
	int iA,jA,iB,jB;
	for(int i = 1; i < n+1; i++)
	{
		ogMatrica[i].resize(n+2);
		for(int j = 0;j <= n; j++)
		{
			char c; int vrednost;
			scanf("%1c",&c);
			if(c  == 'A')
			{
				vrednost = -1;
				iA = i;
				jA = j;
			}
			else if(c == 'B')
			{
				vrednost = -2;
				iB = i;
				jB = j;
			}
			else if(c == '.')
			{
				vrednost = -3;
			}
			else if (c == 'X')
			{
				vrednost = -4;
			}
			else
				vrednost = -5;
			ogMatrica[i][j] = vrednost;
		}
	}
	ogMatrica[0].resize(n+2);
	std::fill(ogMatrica[0].begin(),ogMatrica[0].end(),-5);
	for(int i = 0;i <= n;i++)
	{
		ogMatrica[i][n+1] = -5;
	}
	ogMatrica[n+1].resize(n+2);
	std::fill(ogMatrica[n+1].begin(),ogMatrica[n+1].end(),-5);
	int l = 1;
	int r = maxK;
	int mid;
	while(l <= r)
	{
		mid = l + (r-l)/2;
		int rezZaK = BFSbombe(mid,ogMatrica,iA,jA,n);
		if(rezZaK > brBombi)
			l = mid+1;
		else 
			r = mid-1;
	}
	printf("%d",l);
	return 0;
}