#include <bits/stdc++.h>

using i64 = long long;

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

int f[5001 * 5001];

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

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k;
    std::cin >> n >> k;
    
    std::vector<std::string> s(n);
    for (int i = 0; i < n; i++) {
        std::cin >> s[i];
    }
    
    std::vector dis(n, std::vector<int>(n, -1));
    std::queue<std::pair<int, int>> q;
    q.emplace(0, 0);
    dis[0][0] = 0;
    
    std::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 (true) {
            int u = find(x * (n + 1) + y);
            int nx = u / (n + 1), ny = u % (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;
        }
    }
    
    std::cout << dis[n - 1][n - 1] << "\n";
    
    return 0;
}