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

constexpr int dx[4] = {0, 0, -1, 1};
constexpr int dy[4] = {-1, 1, 0, 0};
int dis[5006][5006];
int f[5001 * 5001];

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

int main() {

    int n, k;
    cin >> n >> k;
    for(int i=0;i<5006;i++)
    {
        for(int j=0;j<5006;j++)dis[i][j]=-1;
    }
    dis[0][0]=0;
    vector<std::string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    queue<std::pair<int, int>> q;
    q.emplace(0, 0);
    
    iota(f, f + (n + 1) * (n + 1), 0);
    
    while (!q.empty()) {
        int x=q.front().first;
        int y=q.front().second;
        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;
        }
    }
    
    cout << dis[n - 1][n - 1] << "\n";
    
    return 0;
}