#include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define fi first #define se second using ll = long long; const ll MAXN = 805; ll bees_dist[MAXN][MAXN]; bool vis[MAXN][MAXN]; ll dx[] = {1, -1, 0, 0}; ll dy[] = {0, 0, 1, -1}; void solve() { ll n, s; cin >> n >> s; vector<string> a(n, string(n, '?')); pair<ll, ll> bear_coord; vector<pair<ll, ll>> bees_coord; for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { cin >> a[i][j]; if (a[i][j] == 'M') bear_coord = {i, j}; if (a[i][j] == 'H') bees_coord.push_back({i, j}); } } auto good = [&](ll t) -> bool { memset(vis, 0, sizeof(vis)); queue<pair<ll, ll>> q; q.push(bear_coord); vis[bear_coord.fi][bear_coord.se] = 1; if (t >= bees_dist[bear_coord.fi][bear_coord.se]) return false; while (!q.empty()) { for (ll k = 0; k < s; k++) { ll sz = q.size(); while (sz--) { auto[x, y] = q.front(); q.pop(); if (a[x][y] == 'D') return true; for (ll i = 0; i < 4; i++) { ll nx = x + dx[i]; ll ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; if (a[nx][ny] == 'T' || a[nx][ny] == 'H') continue; if (t >= bees_dist[nx][ny]) continue; if (vis[nx][ny]) continue; vis[nx][ny] = 1; q.push({nx, ny}); } } } t++; } return false; }; auto bfs = [&](const vector<pair<ll, ll>>& srcs) { for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { bees_dist[i][j] = 1e18; } } queue<pair<ll, ll>> q; for (auto[x, y] : srcs) { q.push({x, y}); bees_dist[x][y] = 0; } while (!q.empty()) { auto[x, y] = q.front(); q.pop(); if (vis[x][y]) continue; vis[x][y] = 1; for (ll i = 0; i < 4; i++) { ll nx = x + dx[i]; ll ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; if (a[nx][ny] != 'G' && a[nx][ny] != 'M') continue; if (bees_dist[nx][ny] > bees_dist[x][y] + 1) { bees_dist[nx][ny] = bees_dist[x][y] + 1; q.push({nx, ny}); } } } }; bfs(bees_coord); ll l = -1, r = 1; while (good(r)) r*=2; while (r > l+1) { ll m = (l+r)/2; if (good(m)) l = m; else r = m; } cout << l << '\n'; } int main() { // freopen("atlarge.in", "r", stdin); // freopen("atlarge.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); }