#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n, k;
int dx[5] = { 0, 1, -1, 0, 0 };
int dy[5] = { 0, 0, 0, 1, -1 };
char map[1010][1010];
bool flag[1010][1010] = { false };
queue<pair< pair<int, int>, pair<int,int> > > p;
void bfs()
{
	int r, c, ans, rt;
	while (!p.empty())
	{
		int x = p.front().first.first, y = p.front().first.second;
		ans = p.front().second.first, rt = p.front().second.second;
		p.pop();
		if (x == n && y == n)
		{
			cout << ans;
			return;
		}
		if (map[x][y] == '%' && flag[x][y])
		{
			rt = k;
			flag[x][y] = false;
		}
		for (int i = 1; i <= 4; i++)
		{
			r = x + dx[i], c = y + dy[i];
			if (r < 1 || r > n || c < 1 || c > n || map[r][c] == '#' || (map[r][c] == 'X' && rt <= 0))
				continue;
			//vis[r][c] = true;
			p.push({ { r, c },{ans + 1,rt - 1} });
		}
		rt--;
	}
}
int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			cin >> map[i][j];
			if (map[i][j] == '%')
				flag[i][j] = true;
		}
	}
	//vis[1][1] = true;
	p.push({ {1,1},{0,0} });
	bfs();
	return 0;
}