#include<bits/stdc++.h>
using namespace std;
char a[1010][1010];//地图数组 
int b[1010][1010]/*记录是否走过*/,c[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int d[1010][1010]/*记录是否无敌状态*/,e[1010][1010]/*步数数组*/,n,m;
void bfs(int x,int y)
{
	int hx[1010]={0},hy[1010]={0};
	int h1=0,h2=0,sum=0;
	hx[h1]=x;hy[h1]=y;
	b[x][y]=0,e[x][y]=0;
	h2++;
	while(h1<h2)
	{
		
		if(hx[h1]==n&&hy[h1]==n)return;
		for(int i=0;i<4;i++)
		{
			int sth=0;
			int tx=hx[h1]+c[i][0],ty=hy[h1]+c[i][1];
			if(d[hx[h1]][hy[h1]]==0){
				sth=0;
			}else{
				sth=d[hx[h1]][hy[h1]]-1;//记录现在位置的无敌状态 
			}
			if((tx>0&&tx<=n&&ty>0&&ty<=n&&a[tx][ty]!='#'))
			{
			  if((a[tx][ty]=='X'&&sth!=0)||a[tx][ty]=='.'||a[tx][ty]=='%'){
			
				if(a[tx][ty]=='%')
				{
					e[tx][ty]=e[hx[h1]][hy[h1]]+1;//上一步的步数+1 
					d[tx][ty]=m+1;
					a[tx][ty]='.';//防止第二次获得无敌 
					b[tx][ty]=1;
					hx[h2]=tx;hy[h2]=ty;
					h2++;
				}else{
					if(b[tx][ty]==0){
						e[tx][ty]=e[hx[h1]][hy[h1]]+1;
						d[tx][ty]=sth;
						b[tx][ty]=1;
						hx[h2]=tx;hy[h2]=ty;
						h2++;
					}
					if(sth<=d[tx][ty]){//如果上一次走过时无敌状态好过现在跳过，否则再走一次 
						continue;
					}else{
						e[tx][ty]=e[hx[h1]][hy[h1]]+1;
						d[tx][ty]=sth;
						hx[h2]=tx;hy[h2]=ty;
						h2++;
					}
				}
				
			}else{
				continue;
			}
		
		}else{
			continue;
		}
	}
	h1++; 
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	int sum=0;
	bfs(1,1);
	if(e[n][n]==0){
		printf("-1");
		return 0;
	}
	printf("%d",e[n][n]);
}