#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;
const int INF = 1e9;
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};
int n, k;
string a[N];
// bees_time[x][y] = phút khi ong lần đầu chiếm ô (hive = 0). INF nếu ong không chiếm.
int bees_time[N][N];
bool inside(int x, int y){ return x>=0 && x<n && y>=0 && y<n; }
void compute_bees_time(){
for(int i=0;i<n;i++) for(int j=0;j<n;j++) bees_time[i][j] = INF;
queue<pii> q;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j] == 'H'){
bees_time[i][j] = 0;
q.push({i,j});
}
}
}
while(!q.empty()){
auto cur = q.front(); q.pop();
int x = cur.fi, y = cur.se;
for(int dir=0; dir<4; dir++){
int nx = x + dx[dir], ny = y + dy[dir];
if(!inside(nx, ny)) continue;
// ong chỉ lan tới ô G hoặc M (M treated like G)
if(a[nx][ny] != 'G' && a[nx][ny] != 'M') continue;
if(bees_time[nx][ny] == INF){
bees_time[nx][ny] = bees_time[x][y] + 1;
q.push({nx, ny});
}
}
}
// bees_time at 'D' remains INF (ong không vào D)
}
// Kiểm tra với thời gian chờ t (Mecho đợi t phút trước khi bắt đầu di chuyển)
// Trả true nếu Me có thể tới 'D' sau khi đợi t phút (và tránh ong).
bool can(int t){
// tìm vị trí bắt đầu (M) và đích (D)
int sx=-1, sy=-1, tx=-1, ty=-1;
for(int i=0;i<n;i++) for(int j=0;j<n;j++){
if(a[i][j] == 'M'){ sx = i; sy = j; }
if(a[i][j] == 'D'){ tx = i; ty = j; }
}
if(sx==-1 || tx==-1) return false;
// nếu ong đã tới chỗ M trước hoặc đúng lúc Me còn chờ => fail
if(bees_time[sx][sy] <= t) return false;
// seen: đánh dấu ô Me đã từng đứng ở cuối một phút (không cần lặp lại)
static bool seen[N][N];
for(int i=0;i<n;i++) for(int j=0;j<n;j++) seen[i][j] = false;
queue<pii> curr; // các ô Me có thể đứng vào đầu phút (đầu tiên là sau t phút chờ)
curr.push({sx, sy});
seen[sx][sy] = true;
int time = t; // hiện tại là phút đã trôi (ong đã chiếm bees_time <= time)
while(!curr.empty()){
// BFS multi-source trong 1 phút với depth limit = k
queue<pair<pii,int>> bfsq;
// inbfs để tránh push trùng trong BFS nội bộ
static bool inbfs[N][N];
for(int i=0;i<n;i++) for(int j=0;j<n;j++) inbfs[i][j] = false;
int curr_sz = curr.size();
// push tất cả vị trí hiện tại (đầu phút) vào bfsq như depth=0
while(curr_sz--){
auto p = curr.front(); curr.pop();
int x = p.fi, y = p.se;
// Nếu đang ở D -> success
if(x == tx && y == ty) return true;
// nếu ong đã có ở ô này tại thời điểm bắt đầu phút thì bỏ (an toàn check, nhưng initial check tránh trường hợp)
if(bees_time[x][y] <= time) continue;
bfsq.push({{x,y}, 0});
inbfs[x][y] = true;
}
queue<pii> next; // vị trí Me có thể đứng ở cuối phút (time+1)
while(!bfsq.empty()){
auto cur = bfsq.front(); bfsq.pop();
int x = cur.first.first, y = cur.first.second, d = cur.second;
// Nếu chạm D trong nội bộ phút -> success
if(x == tx && y == ty) return true;
// Me có thể đứng ở ô này vào cuối phút nếu ong chưa tới ô đó ở phút time+1
if(bees_time[x][y] > time + 1 && !seen[x][y]){
next.push({x,y});
seen[x][y] = true;
}
if(d == k) continue;
for(int dir=0; dir<4; dir++){
int nx = x + dx[dir], ny = y + dy[dir];
if(!inside(nx, ny)) continue;
if(inbfs[nx][ny]) continue;
// Me có thể đi qua G hoặc D or M(start)
if(!(a[nx][ny] == 'G' || a[nx][ny] == 'D' || a[nx][ny] == 'M')) continue;
// không thể đi vào ô mà ong đã chiếm trước khi bắt đầu phút này
if(bees_time[nx][ny] <= time) continue;
inbfs[nx][ny] = true;
bfsq.push({{nx, ny}, d+1});
}
}
// tiến sang phút kế
time++;
// chuẩn bị vòng lặp với các vị trí có thể đứng vào đầu phút mới
curr = move(next);
}
return false;
}
void solve(){
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
compute_bees_time();
int l = 0, r = 2 * n, ans = -1;
while(l <= r){
int mid = (l + r) >> 1;
if(can(mid)){
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
