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

#define ll long long
const int N=1e3+10;

struct node{
	int x,y,num,dis;
};

int n,k;
char a[N][N],vis[N][N],f[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
queue<node> q;

inline void BFS(){
	q.push({1,1,0,0});
	while(!q.empty()){
		int xx=q.front().x,yy=q.front().y,num=q.front().num,dis=q.front().dis;
		q.pop();
		if(vis[xx][yy]>=dis||(dis<0&&a[xx][yy]=='X')||a[xx][yy]=='#'||xx<1||xx>n||yy<1||yy>n){
			continue;
		}
		if(a[xx][yy]=='%'){
//			a[xx][yy]='.';
			dis=k;
		}
		if(xx==n&&yy==n){
			cout<<num<<endl;
			return ;
		}
		vis[xx][yy]=dis;
		for(int i=0;i<4;i++){
			q.push({xx+f[i][0],yy+f[i][1],num+1,dis-1});
		}
	}
	cout<<"-1"<<endl;
	return ;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(0);
	cin>>n>>k;
	memset(vis,-0x3f,sizeof(vis));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	BFS();
	return 0;
}