#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
struct Node{
	int x_add, y_add, step, invincible;
};
queue<Node> q;
int vis[1005][1005];
int n, k;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool f = 0;
char c[1005][1005];
void bfs(){
	memset(vis, -1, sizeof(vis));
	vis[1][1] = 0;
	q.push({1, 1, 0, 0});
	while(!q.empty()){
		Node t = q.front();
		if(t.x_add == n && t.y_add == n){
			printf("%d", t.step);
			f = 1;
			break;
		}
		q.pop();
		for(int i = 0; i < 4; i++){
			int nx = t.x_add + dx[i];
			int ny = t.y_add + dy[i];
			if(c[nx][ny] == 'X' && t.invincible == 0)
				continue;
			int invincibles = max(t.invincible - 1, 0);
			if(c[nx][ny] == '%')
				invincibles = k;
			if(nx < 1 || nx > n || ny < 1 || ny > n || vis[nx][ny] > invincibles || c[nx][ny] == '#')
				continue;
			q.push({nx, ny, t.step+1, invincibles});
			vis[nx][ny] = invincibles;
		}
	}
}
int main(){
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			cin >> c[i][j];
	bfs(); 
	if(!f)
		printf("-1");
	return 0;
}