#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ldb long double
#define pii pair<int, int>
#define bend(v) v.begin(), v.end()
const int N = 800 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};
int n, k;
string a[N], b[N];
void ms_bfs(int t){
queue<pair<pii, int>> qu;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(b[i][j] == 'H') qu.push({{i, j}, t});
}
}
while(!qu.empty()){
pii ord = qu.front().first;
int x = ord.first, y = ord.second, remain = qu.front().second;
qu.pop();
if(!remain) continue;
for(int dir = 0; dir < 4; dir++){
int u = x + dx[dir], v = y + dy[dir];
if(u < 0 || u >= n || v < 0 || v >= n) continue;
// cho ong lan vao G HOAC M (M la o bat dau cua Me)
if(b[u][v] != 'G' && b[u][v] != 'M') continue;
b[u][v] = 'H'; qu.push({{u, v}, remain - 1});
}
}
}
vector<pii> mechoo(vector<pii> cur){
vector<pii> tmp;
queue<pair<pii, int>> qu;
for(pii ord : cur){
int x = ord.first, y = ord.second;
if(b[x][y] == 'H') continue;
qu.push({{x, y}, k});
}
while(!qu.empty()){
pii ord = qu.front().first;
int x = ord.first, y = ord.second, remain = qu.front().second;
qu.pop();
// ô này reachable trong <=k bước -> có thể đứng ở đây cuối phút
tmp.push_back({x, y});
if(!remain) continue;
for(int dir = 0; dir < 4; dir++){
int u = x + dx[dir], v = y + dy[dir];
if(u < 0 || u >= n || v < 0 || v >= n) continue;
if(b[u][v] != 'G' && b[u][v] != 'D' && b[u][v] != 'M') continue;
if(b[u][v] == 'H') continue; // ko di vao ong
// dấu visited để khỏi push lại cùng ô nhiều lần trong cùng phút
if(b[u][v] == 'M') continue; // đã đánh dấu
// ta cần đánh dấu để tránh push trùng (chỉ trong mô phỏng này)
b[u][v] = 'M'; qu.push({{u, v}, remain - 1});
}
}
return tmp;
}
bool bfs(){
vector<pii> be1, be2; //bees
vector<pii> me; //mecho
pii en = {-1, -1};
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(b[i][j] == 'M') me.push_back({i, j});
if(b[i][j] == 'H') be1.push_back({i, j});
if(b[i][j] == 'D') en = {i, j};
}
}
if(en.first == -1) return false;
while(!me.empty()){
me = mechoo(me);
if(b[en.fi][en.se] == 'M') return true;
be2.clear();
for(pii ord : be1){
int x = ord.first, y = ord.second;
for(int dir = 0; dir < 4; dir++){
int u = x + dx[dir], v = y + dy[dir];
if(u < 0 || u >= n || v < 0 || v >= n) continue;
if(b[u][v] != 'M' && b[u][v] != 'G' && b[u][v] != 'D') continue;
// ong ko vao D? theo de bai ong ko vao D, neu D la duong ve, khong cho D.
if(b[u][v] == 'D') continue;
if(b[u][v] == 'H') continue;
b[u][v] = 'H'; be2.push_back({u, v});
}
}
be1.clear(); swap(be1, be2);
}
return false;
}
bool check(int t){
for(int i = 0; i < n; i++) b[i] = a[i];
ms_bfs(t);
return bfs();
}
void solve(){
cin>>n>>k;
for(int i = 0; i < n; i++) cin>>a[i];
int l = 0, r = n * n, mid; // <-- để r = n*n thay vì 2*n
int ans = -1;
while(l <= r){
mid = (l + r) >> 1;
if(check(mid)){ ans = mid; l = mid + 1; }
else r = mid - 1;
}
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
