#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,k;
char mp[N][N];
bool fl[N][N];//普通标记
bool fk[N][N];//无敌标记，不同标记以防止重复遍历图
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};

struct node {
	int x,y,k,cnt;
	node() {};
	node(int a,int b,int c,int d):x(a),y(b),k(c),cnt(d) {};
} e,nx;

queue<node> q;
void bfs() {
	q.emplace(1,1,0,0);//加入起点
	fl[1][1]=true;
	fk[1][1]=true;

	while(!q.empty()) {
		e=q.front();
		q.pop();
		if(e.x==n&&e.y==n) {
			cout<<e.cnt;
			return;
		}
		
		e.cnt++;	  //扩展下一步
		if(e.k)e.k-=1;//当前若是无敌状态则每一步开始前k减一
		
		for(int i=0; i<4; i++) {
			nx=e;
			nx.x+=dx[i];
			nx.y+=dy[i];
			if(nx.x>=1&&nx.x<=n&&nx.y>=1&&nx.y<=n&&mp[nx.x][nx.y]!='#') {
				if(mp[nx.x][nx.y]=='%')nx.k=k;	//获得无敌状态

				if(nx.k&&!fk[nx.x][nx.y]) {	//无敌状态扩展
					fk[nx.x][nx.y]=true;
					q.emplace(nx);
					continue;
				}

				if(mp[nx.x][nx.y]!='X'&&!fl[nx.x][nx.y]) {//普通状态扩展
					fl[nx.x][nx.y]=true;
					q.emplace(nx);
				}
			}
		}
	}
	cout<<-1;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	k+=1;//玄学加一正常运行
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			cin>>mp[i][j];
	bfs();

//	cout<<endl; 调试经过路径
//	for(int i=1; i<=n; i++) {
//		for(int j=1; j<=n; j++)
//			cout<<fl[i][j];
//		cout<<endl;
//	}
//
//	cout<<endl;
//	for(int i=1; i<=n; i++) {
//		for(int j=1; j<=n; j++)
//			cout<<fk[i][j];
//		cout<<endl;
//	}
	return 0;
}