#include <bits/stdc++.h> using namespace std; #define ll long long #define fr(i,a,b,c) for(ll i = a;i<b;i+=c) #define fre(i,a,b,c) for(int i = a;i>=b;i-=c) #define fs first #define sc second #define all(a) a.begin(),a.end() #define IINF 2000000005 #define LINF 1000000000000000005 #define str string #define endl '\n' using pii = pair<int,int>; using pll = pair<ll,ll>; using tiii = tuple<int,int,int>; using tiiii = tuple<int,int,int,int>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); } ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); } int dx[4] = {0,0,-1,1}; int dy[4] = {-1,1,0,0}; constexpr int MOD = 1000000007; //998244353 str a[805]; int n,k; int pf[805][805]; bool vis[805][805]; int sx,sy,ex,ey; bool ch(int m){ fr(i,0,n,1)fill(vis[i],vis[i] + n,0); if(pf[sx][sy] <= m)return 0; queue<tiiii> q; q.push({m + 1,k,sx,sy}); vis[sx][sy] = 1; while(!q.empty()){ auto [t,d,x,y] = q.front(); q.pop(); if(d == 0){ // if(pf[x][y] == t){ // vis[x][y] = 0; // continue; // } t++; d = k; } // cout << x << ' ' << y << ' ' << t << ' ' << d << endl; fr(i,0,4,1){ int nx = x + dx[i]; int ny = y + dy[i]; if(nx >= 0 && nx < n && ny >= 0 && ny < n && a[nx][ny] != 'T' && !vis[nx][ny] && pf[nx][ny] >= t){ if(pf[nx][ny] == t && d == 1)continue; vis[nx][ny] = 1; q.push({t,d - 1,nx,ny}); } } } // fr(i,0,n,1){ // fr(j,0,n,1)cout << vis[i][j] << ' ';cout << endl; // } return vis[ex][ey]; } int main(){ cin >> n >> k; fr(i,0,n,1)cin >> a[i]; fr(i,0,n,1)fill(pf[i],pf[i] + n,IINF); queue<tiii> q; fr(i,0,n,1){ fr(j,0,n,1){ if(a[i][j] == 'H'){ vis[i][j] = 1; pf[i][j] = 0; q.push({0,i,j}); } if(a[i][j] == 'M'){ sx = i; sy = j; } if(a[i][j] == 'D'){ ex = i; ey = j; } } } while(!q.empty()){ auto [d,x,y] = q.front(); pf[x][y] = d; q.pop(); fr(i,0,4,1){ int nx = x + dx[i]; int ny = y + dy[i]; if(nx >= 0 && nx < n && ny >= 0 && ny < n && (a[nx][ny] == 'G' || a[nx][ny] == 'M') && !vis[nx][ny]){ vis[nx][ny] = 1; q.push({d + 1,nx,ny}); } } } int l = 0,r = 1e9,ans = -1; while(l <= r){ int m = (l + r)/2; if(ch(m)){ l = m + 1; ans = m; }else{ r = m - 1; } } cout << ans << endl;; // fr(i,0,n,1){ // fr(j,0,n,1)cout << (pf[i][j] == IINF ? -1 : pf[i][j]) << ' ';cout << endl; // } // ch(3); }