#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int , int> pi; typedef pair<ll , ll> pll; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<ll> vll; typedef vector<vi> vvi; typedef vector<vll> vvll; #define pb push_back #define lb lower_bound #define up upper_bound #define F first #define S second #define nd "\n" #define forad(i , a , b) for(int i = a; i < (int) b; i++) #define forat(i , a , b) for(int i = a; i >= b; i--) #define debug(x) cout << #x << " = " << x << nd #define debugv(x , s) cout << #x << " = " << forad(i , 0 , s) cout << x[i] << " "; cout << nd #define faster ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define all(x) x.begin() , x.end() const ll mod = 1e9+7 , INF = 1e9; ll inv(ll x){return x <= 1 ? x : (mod - mod/x) * inv(mod%x) % mod;} #define smod(a , b) (a%mod+b%mod)%mod #define rmod(a , b) (a%mod - b%mod + mod)%mod #define mmod(a , b) (a%mod) * (b%mod)%mod #define dmod(a , b) (a%mod) * inv(b) %mod int n, s; vector<string> a; queue<pi> q; vvi dist; const int dx[4] = {-1, 0, 1, 0}; const int dy[4] = {0, -1, 0, 1}; bool pasabee(int x , int y){ if (x < 0 || y < 0 || x >= n || y >= n) return false; if (a[x][y] == 'T') return false; if (a[x][y] == 'D') return false; return true; } void ffbees() { while (!q.empty()) { pi front = q.front(); q.pop(); forad(d , 0 , 4){ int nx = front.F + dx[d], ny = front.S + dy[d]; if(!pasabee(nx , ny)) continue; if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; if (dist[front.F][front.S] + 1 < dist[nx][ny]) { dist[nx][ny] = dist[front.F][front.S] + 1; q.push({nx, ny}); } } } } vvi bees(const vector<pi> ini) { dist.assign(n, vi(n, INF)); while (!q.empty()) q.pop(); for (auto x : ini) { dist[x.F][x.S] = 0; q.push({x.F , x.S}); } ffbees(); return dist; } bool cumple(int x, int y) { if (x < 0 || y < 0 || x >= n || y >= n) return false; return a[x][y] == 'G' || a[x][y] == 'M'; } bool puedo(int mt, int bt) {return mt / s < bt;} bool mechoff(int sx, int sy, int tx, int ty, const vvi bt, int w) { dist.assign(n, vi(n, INF)); while (!q.empty()) q.pop(); if (bt[sx][sy] <= w) return false; dist[sx][sy] = 0; q.push({sx, sy}); while (!q.empty()) { pi front = q.front(); q.pop(); int t = dist[front.F][front.S] + 1; forad(d , 0 , 4) { int nx = front.F + dx[d], ny = front.S + dy[d]; if(!cumple(nx , ny))continue; if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; if (t >= dist[nx][ny]) continue; int quedan = bt[nx][ny] - w; if(quedan <= 0) continue; if (puedo(t, quedan)) { dist[nx][ny] = t; q.push({nx, ny}); } } } forad(d , 0 , 4) { int nx = tx + dx[d], ny = ty + dy[d]; if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; if (!cumple(nx, ny)) continue; if (dist[nx][ny] == INF) continue; if (puedo(dist[nx][ny], bt[nx][ny] - w)) return true; } return false; } int main() { faster; cin >> n >> s; a.resize(n); forad(i, 0, n) cin >> a[i]; int sx, sy, tx, ty; vector<pi> ini; forad(i, 0, n) { forad(j, 0, n) { if (a[i][j] == 'M') sx = i, sy = j; if (a[i][j] == 'H') ini.pb({i, j}); if (a[i][j] == 'D') tx = i, ty = j; } } vvi bt = bees(ini); int l = 0, r = n * n , m; while (l <= r) { m = l + (r - l) / 2; if (mechoff(sx, sy, tx, ty, bt, m)) l = m + 1; else r = m - 1; } cout << r << nd; }