#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) {
    if (f[x] != x)
        f[x] = find(f[x]);
    return f[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 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';
    return 0;
}