#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
    
const int MOD = 1e9 + 7;
const int MAXN = 5e3 + 5;
const ll INF = 2e18;

bool tb[MAXN][MAXN];

pii pai[MAXN][MAXN];
pii mx[MAXN][MAXN];
int qt[MAXN][MAXN];
int dist[MAXN][MAXN];

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

int n, k;

pii find(pii cur) {
    if(cur == pai[cur.first][cur.second]) return cur;
    return pai[cur.first][cur.second] = find(pai[cur.first][cur.second]);
}

void une(pii a, pii b) {
    a = find(a); b = find(b);
    if(a == b) return;
    if(qt[a.first][a.second] > qt[b.first][b.second]) swap(a, b);
    qt[b.first][b.second] += qt[a.first][a.second];
    pai[a.first][a.second] = b;
    if(mx[a.first][a.second].first + mx[a.first][a.second].second > mx[b.first][b.second].first + mx[b.first][b.second].second) mx[b.first][b.second] = mx[a.first][a.second];
    //mx[b.first][b.second] = max(mx[b.first][b.second], mx[a.first][a.second]);
}

pii ant(pii cur) {
    if(cur.first == 1) return cur;
    return {cur.second, cur.first - 1};
}

pii prox(pii cur) {
    return {cur.second + 1, cur.first};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < n; j++) {
            if(s[j] == '.') {
                tb[i][j + 1] = 0;
            }
            else {
                tb[i][j + 1] = 1;
            }
            pai[i][j + 1] = {i, j + 1};
            mx[i][j + 1] = {i, j + 1};
            qt[i][j + 1] = 1;
        }
    }
    queue <pii> fila;
    fila.push({1, 1});
    tb[1][1] = 1;
    dist[n][n] = -1;
    while(!fila.empty()) {
        pii cur = fila.front(); fila.pop();
        //cout << cur.first << ' ' << cur.second << ' ' << dist[cur.first][cur.second] << endl;
        une(cur, ant(cur));
        for(int i = 0; i < 4; i++) {
            int vx = dx[i] + cur.first, vy = dy[i] + cur.second;
            if(vx < 1 || vx > n || vy < 1 || vy > n) continue;
            if(tb[vx][vy] == 1) continue;
            tb[vx][vy] = 1;
            dist[vx][vy] = dist[cur.first][cur.second] + 1;
            fila.push({vx, vy});
            une({vx, vy}, ant({vx, vy}));
        }
        pii rz = find(cur);
        pii at = prox(mx[rz.first][rz.second]);
        while(at.first <= n && at.second <= n && at.first + at.second - cur.first - cur.second <= k) {
            if(tb[at.first][at.second] == 0) {
                tb[at.first][at.second] = 1;
                dist[at.first][at.second] = dist[cur.first][cur.second] + 1;
                fila.push(at);
            }
            une(at, ant(at));
            rz = find(at);
            at = prox(mx[rz.first][rz.second]);
            //cout << "at: " << at.first << ' ' << at.second << ' ' << rz.first << ' ' << rz.second << endl;
        }
    }
    cout << dist[n][n] << '\n';
    return 0;
}