#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int MAXN = 5e3 + 100;
string s[MAXN];
int d[MAXN][MAXN][5];

vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < k; ++i) {
		cin >> s[i];
	}

	auto check = [&](int i, int j) {
		if (i < 0 || i >= n || j < 0 || j >= n || s[i][j] == '*') return false;
		return true;
	};

	deque<array<int, 3>> q;
	q.push_back({0, 0, 0});

	auto get_i = [&](array<int, 3> a) {
		if (a[2] == 0) return 2;
		int pos = abs(a[2]) - (k + 1) / 2;
		if (a[2] > 0) return pos + 3;
		return pos;
	};

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			for (int t = 0; t < 5; ++t) {
				d[i][j][t] = n * n;
			}
		}
	}
	d[0][0][2] = 0;

	while (!q.empty()) {
		int i = q.front()[0], j = q.front()[1], l = q.front()[2];
		/// cerr << i << " " << j << " " << l << endl;
		q.pop_front();
		if (l == 0) {
			for (int t = 0; t < 4; ++t) {
				int i1 = i + dx[t], j1 = j + dy[t];
				/// cerr << i1 << " " << " " << j1 << endl;
				if (check(i1, j1) && d[i1][j1][2] > d[i][j][2] + 1) {
					d[i1][j1][2] = d[i][j][2] + 1;
					q.push_back({i1, j1, 0});
				}
			}

			auto add = [&](int i, int j, int l, int w) {
				if (d[i][j][get_i({i, j, l})] > w) {
					d[i][j][get_i({i, j, l})] = w;
					q.push_back({i, j, l});
				}
				int i1 = i + l - 1;
				int j1 = j + l - 1;
				if (i1 >= n) {
					j1 -= (i1 - n + 1);
					i1 -= (i1 - n + 1);
				}
				if (j1 >= n) {
					i1 -= (j1 - n + 1);
					j1 -= (j1 - n + 1);
				}
				if ((i + j + 2 * l - 2) / (2 * l) == (i1 + j1 + 2 * l - 2) / (2 * l)) return;
				if (d[i1][j1][get_i({i1, j1, -l})] > w) {
					d[i1][j1][get_i({i1, j1, -l})] = w;
					q.push_back({i1, j1, -l});
				}
			};

			int l = (k + 2) / 2;
			int w = d[i][j][2] + 1;
			add(i, j, l, w);
			if (j + 1 < n) {
				l = (k + 1) / 2;
				add(j + 1, i, l, w);
			}
		} else {
			if (check(i, j) && d[i][j][2] > d[i][j][get_i({i, j, l})]) {
				d[i][j][2] = d[i][j][get_i({i, j, l})];
				q.push_front({i, j, 0});
			}
			if (((i + j) / 2) % abs(l) == 0) continue;
			int i1, j1;
			if (l > 0) {
				i1 = i + 1;
				j1 = j + 1;
			} else {
				i1 = i - 1;
				j1 = j - 1;
			}
			if (i1 >= 0 && i1 < n && j1 >= 0 && j1 < n) {
				if (d[i1][j1][get_i({i1, j1, l})] > d[i][j][get_i({i, j, l})]) {
					d[i1][j1][get_i({i1, j1, l})] = d[i][j][get_i({i, j, l})];
					q.push_front({i1, j1, l});
				}
			}
		}
	}

	if (d[n - 1][n - 1][2] == n * n) {
		cout << "-1\n";
	} else {
		cout << d[n - 1][n - 1][2] << "\n";
	}

	return 0;
}