#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x,y,step,k;
};
int n,k;
char a[1005][1005];
bool vis[1005][1005];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void bfs(int x,int y)
{
	queue<node> q;
	q.push(node{x,y,0,0});
	vis[x][y]=1;
	while(!q.empty())
	{
		node u=q.front();
		q.pop();
		if(u.x==n&&u.y==n)
		{
			cout<<u.step<<endl;
			return;
		}
		for(int i=0;i<4;i++)
		{
			int bx=u.x+dx[i];
			int by=u.y+dy[i];
			if(bx<1||bx>n||by<1||by>n)
			{
				continue;
			}
			else if(vis[bx][by])
			{
				continue;
			}
			else if(a[bx][by]=='#')
			{
				continue;
			}
			else if(a[bx][by]=='X'&&u.k==0)
			{
				continue;
			}
			else if(a[bx][by]=='X')
			{
				vis[bx][by]=1;
				q.push(node{bx,by,u.step+1,u.k-1});
			}
			else if(a[bx][by]=='%')
			{
				vis[bx][by]=1;
				q.push(node{bx,by,u.step+1,k});
			}
		}
	}
	cout<<-1<<endl;
	return;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	bfs(1,1);
    return 0;
}
/*
*/