#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int MAXN = 805;
const int INF = 1e9;
int n, k;
string a[MAXN];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int bees_time[MAXN][MAXN];
int sx=-1, sy=-1, tx=-1, ty=-1;
inline int id(int x, int y){ return x * n + y; }
inline int xi(int idd){ return idd / n; }
inline int yi(int idd){ return idd % 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});
}
if(a[i][j] == 'M'){ sx=i; sy=j; }
if(a[i][j] == 'D'){ tx=i; ty=j; }
}
}
while(!q.empty()){
auto cur = q.front(); q.pop();
int x = cur.first, y = cur.second;
for(int dir=0; dir<4; ++dir){
int nx = x + dx[dir], ny = y + dy[dir];
if(nx<0||nx>=n||ny<0||ny>=n) continue;
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[tx][ty] stays INF (bees don't enter D)
}
// --- token arrays to avoid memset ---
static int seen_mark[MAXN*MAXN];
static int inbfs_mark[MAXN*MAXN];
static int seen_token = 2;
static int inbfs_token = 4;
// static arrays to avoid allocations
static int curr_arr[MAXN*MAXN];
static int next_arr[MAXN*MAXN];
static int qnodes[MAXN*MAXN];
static int qdepth[MAXN*MAXN];
bool can(int t){
if(sx==-1 || tx==-1) return false;
if(bees_time[sx][sy] <= t) return false;
int curr_sz = 0;
curr_arr[curr_sz++] = id(sx, sy);
++seen_token; if(seen_token==0){ ++seen_token; ++inbfs_token; }
++inbfs_token; if(inbfs_token==0){ ++inbfs_token; ++seen_token; }
int time = t;
while(curr_sz){
// BFS multi-source limited to depth k
int qhead = 0, qtail = 0;
++inbfs_token; if(inbfs_token==0){ ++inbfs_token; ++seen_token; }
// push all current
for(int i=0;i<curr_sz;i++){
int pos = curr_arr[i];
int x = xi(pos), y = yi(pos);
if(bees_time[x][y] <= time) continue; // unsafe at start
if(x==tx && y==ty) return true;
if(inbfs_mark[pos] != inbfs_token){
inbfs_mark[pos] = inbfs_token;
qnodes[qtail] = pos;
qdepth[qtail] = 0;
++qtail;
}
}
int next_sz = 0;
while(qhead < qtail){
int curpos = qnodes[qhead];
int d = qdepth[qhead];
++qhead;
int x = xi(curpos), y = yi(curpos);
if(x==tx && y==ty) return true;
if(bees_time[x][y] > time + 1 && seen_mark[curpos] != seen_token){
seen_mark[curpos] = seen_token;
next_arr[next_sz++] = curpos;
}
if(d == k) continue;
for(int dir=0; dir<4; ++dir){
int nx = x + dx[dir], ny = y + dy[dir];
if(nx<0||nx>=n||ny<0||ny>=n) continue;
char ch = a[nx][ny];
if(!(ch=='G' || ch=='D' || ch=='M')) continue;
if(bees_time[nx][ny] <= time) continue;
int nid = id(nx,ny);
if(inbfs_mark[nid] == inbfs_token) continue;
inbfs_mark[nid] = inbfs_token;
qnodes[qtail] = nid;
qdepth[qtail] = d+1;
++qtail;
}
}
time++;
++seen_token; if(seen_token==0){ ++seen_token; ++inbfs_token; }
// swap curr and next
curr_sz = next_sz;
for(int i=0;i<next_sz;i++) curr_arr[i] = next_arr[i];
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
if(!(cin >> n >> k)) return 0;
for(int i=0;i<n;i++) cin >> a[i];
compute_bees_time();
// set upper bound r more tightly:
int r;
if(bees_time[sx][sy] == INF) r = n * n; // bees never reach M -> cap at n*n
else r = min(n * n, bees_time[sx][sy] - 1); // cannot wait >= bees_time[sx][sy]
int l = 0, 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';
return 0;
}
