#include <iostream>
struct node {
	int x, y;
	int step;
	int type;
};
struct Queue {
	node u[1010100];
	int head = 0, tail = 0;
	inline void reuse() {
		head = 0, tail = 0;
	}
	inline void push(node a) {
		u[tail] = a;
		tail = (tail + 1) % 1000000;
	}
	inline void pop() {
		head = (head + 1) % 1000000;
	}
	inline node front() {
		return u[head];
	}
	inline node back() {
		return u[tail];
	}
	inline int size() {
		return tail - head + 1;
	}
	inline bool empty() {
		return tail == head;
	}
} q;
char Getchar() {
	char c = getchar();
	while (c != '+' && c != '*') c = getchar();
	return c;
}
char a[1010][1010];
bool vis[1010][1010];
int n, k;
int dir[4][2] = {
	{0, 1},
	{1, 0},
	{0, -1},
	{-1, 0}
};
bool pd(int x, int y, int bc) {
	for (int i = x - bc; i <= x + bc; ++i) {
		for (int j = y - bc; j <= y + bc; ++j) {
			if (i < 1 || j < 1 || i > n || j > n || a[i][j] == '*') {
				return 0;
			}
		}
	}
	return 1;
}
void bfs(int x, int y) {
	q.push({x, y, 0, 0});
	while (!q.empty()) {
		node frt = q.front();
		q.pop();
		if (frt.x == n - 2 && frt.y == n - 2) {
			printf("%d\n", frt.step);
			return ;
		}
		if (frt.step % k == 0 && frt.step != 0) {
			frt.type++;
		}
		if (frt.type < 2) {
			q.push({frt.x, frt.y, frt.step + 1, frt.type});
		}
		for (int i = 0; i < 4; ++i) {
			int _x = frt.x + dir[i][0], _y = frt.y + dir[i][1];
			if (frt.type == 0) {
				if (pd(_x, _y, 2)) {
					if (vis[_x][_y]) continue;
					vis[_x][_y] = 1;
					q.push({_x, _y, frt.step + 1, frt.type});
				};
			} else if (frt.type == 1) {
				if (pd(_x, _y, 1)) {
					if (vis[_x][_y]) continue;
					vis[_x][_y] = 1;
					q.push({_x, _y, frt.step + 1, frt.type});
				};
			} else if (pd(_x, _y, 0)) {
				if (vis[_x][_y]) continue;
				vis[_x][_y] = 1;
				q.push({_x, _y, frt.step + 1, frt.type});
			};
		}
	}
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			a[i][j] = Getchar();
		}
	}
	bfs(3, 3);
	return 0;
}

具体哪挂了不清楚，可能是手写的队列可能其他地方