#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; bool beesvis[MAXN][MAXN]; bool bearvis[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(beesvis, 0, sizeof(beesvis)); memset(bearvis, 0, sizeof(bearvis)); queue<pair<ll, ll>> beesq, bearq; // false ako se vise nisu sirile u ovom potezu auto bees = [&]() -> bool { bool ret = false; ll sz = beesq.size(); while (sz--) { auto[x, y] = beesq.front(); beesq.pop(); 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 (beesvis[nx][ny]) continue; if (a[nx][ny] != 'G') continue; beesvis[nx][ny] = 1; ret = true; beesq.push({nx, ny}); } } return ret; }; // true ako je dosao do kuce auto bear = [&]() -> bool { ll sz = bearq.size(); while (sz--) { auto[x, y] = bearq.front(); bearq.pop(); if (beesvis[x][y]) continue; 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] == 'D') return true; if (a[nx][ny] != 'G') continue; if (beesvis[nx][ny] || bearvis[nx][ny]) continue; bearvis[nx][ny] = 1; bearq.push({nx, ny}); } } return false; }; for (auto[x, y] : bees_coord) { beesq.push({x, y}); beesvis[x][y] = 1; } bearq.push(bear_coord); bearvis[bear_coord.fi][bear_coord.se] = 1; while (t--) bees(); while (1) { for (ll i = 0; i < s; i++) { if (bear()) return true; } if (!bees()) return false; } }; 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(); }