#include<bits/stdc++.h>
using i64 = long long;
using namespace std;

const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};

int f[5001 * 5001];

int find(int x) {
    int t = x;
    while (f[x] != x) {
        x = f[x];
    }
    while (f[t] != t) {
        t = f[t];
        f[t] = x;
    }
    return x;
}

void solve() {
    int n, k; cin >> n >> k;
    vector<string> s(n);
    for (int i = 0; i < n; ++i) cin >> s[i];
    vector dis(n, vector<int>(n, -1));
    queue<pair<int, int>> q;
    q.emplace(0, 0);
    dis[0][0] = 0;

    iota(f, f + (n + 1) * (n + 1), 0);
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < n && dis[nx][ny] == -1 && s[nx][ny] == '.') {
                q.emplace(nx, ny);
                dis[nx][ny] = dis[x][y] + 1;
            }
        }
        while (1) {
            int p = find(x * (n + 1) + y);
            int nx = p / (n + 1), ny = p % (n + 1);
            if (nx == n || ny == n || nx + ny > x + y + k)
                break;
            if (dis[nx][ny] == -1 && s[nx][ny] == '.') {
                q.emplace(nx, ny);
                dis[nx][ny] = dis[x][y] + 1;
            }
            f[nx * (n + 1) + ny] = (ny + 1) * (n + 1) + nx;
        }
    }
    cout << dis[n - 1][n - 1] << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T--)
        solve();
    return 0;
}