#include<bits/stdc++.h>
using namespace std;
#define int long long
struct st{
	int x , y , k , sp ;
};        //定义结构体
int mp[1005][1005] ;  //数字地图
int n , k ;
char c[1005][1005] ;  //字符地图
int dx[] = { 0  , 1 , 0 , -1 } ;  
int dy[] = { -1 , 0 , 1 ,  0 } ;   //dfs路线
queue<st> que ;   //定义队列
signed main()
{
	cin >> n >> k ;
	memset( mp , -1 , sizeof( mp ) ) ;  //memset复值-1
	for ( int i = 1 ; i <= n ; i++ ){
		for ( int j = 1 ; j <= n ; j++ ){
			cin >> c[i][j] ;
		}
	}  //无脑输入
	que.push( { 1 , 1 , 0 , 0 } ) ;   //将第一个的信息放入队列
	mp[1][1] = 0 ;
	while( !que.empty() ){
		st head = que.front() ;   //取出第一个
		que.pop() ;  //弹出第一个
		int sp = head.sp + 1 ;  // 定义step
		for ( int kk = 0 ; kk <= 3 ; kk++ ){
			int xx = head.x + dx[kk] ;  //走的行数
			int yy = head.y + dy[kk] ;  //走的列数
			if ( xx < 1 || xx > n || yy < 1 || yy > n )	continue ;  //判断是否越界
			if ( xx == n && yy == n ){
				cout << sp ;
				return 0 ;
			}    //到达终点
			int wd = head.k ;   //无敌时间
			if ( c[xx][yy] == '#' )	continue ;  //判断是否是墙壁
			if ( c[xx][yy] == 'X' && wd == 0 )	continue ;  //碰到陷阱并没有无敌时间
			wd-- ;  //无敌时间-1
			if ( wd < 0 )	wd = 0 ;	//处理
			if ( c[xx][yy] == '%' ){
				wd = k ;
				c[xx][yy] = '.' ;    //道具
			}	
			if ( mp[xx][yy] >= wd )	continue ;
			que.push( { xx , yy , wd , sp } ) ;
			mp[xx][yy] = wd ;  //赋值mp地图
		}
	}
	cout << -1 ;   //没有输出最后输出-1
	return 0 ;     //好习惯的养成qwq
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct st{
	int x , y , k , sp ;
};
int mp[1005][1005] ;
int n , k ;
char c[1005][1005] ;
int dx[] = { 0  , 1 , 0 , -1 } ;
int dy[] = { -1 , 0 , 1 ,  0 } ;
queue<st> que ;
signed main()
{
	cin >> n >> k ;
	memset( mp , -1 , sizeof( mp ) ) ;
	for ( int i = 1 ; i <= n ; i++ ){
		for ( int j = 1 ; j <= n ; j++ ){
			cin >> c[i][j] ;
		}
	}
	que.push( { 1 , 1 , 0 , 0 } ) ;
	mp[1][1] = 0 ;
	while( !que.empty() ){
		st head = que.front() ;
		que.pop() ;
		int sp = head.sp + 1 ;
		for ( int kk = 0 ; kk <= 3 ; kk++ ){
			int xx = head.x + dx[kk] ;
			int yy = head.y + dy[kk] ;
			if ( xx < 1 || xx > n || yy < 1 || yy > n )	continue ;
			if ( xx == n && yy == n ){
				cout << sp ;
				return 0 ;
			}
			int wd = head.k ;
			if ( c[xx][yy] == '#' )	continue ;
			if ( c[xx][yy] == 'X' && wd == 0 )	continue ;
			wd-- ;
			if ( wd < 0 )	wd = 0 ;	
			if ( c[xx][yy] == '%' ){
				wd = k ;
				c[xx][yy] = '.' ;
			}	
			if ( mp[xx][yy] >= wd )	continue ;
			que.push( { xx , yy , wd , sp } ) ;
			mp[xx][yy] = wd ;
		}
	}
	cout << -1 ;
	return 0 ;
}