#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
// === Debug macro starts here ===
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) \
{ \
++recur_depth; \
auto x_ = x; \
--recur_depth; \
cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":" \
<< __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl; \
}
#else
#define dbg(x)
#endif
template <typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(
Ostream& os, const Cont& v) {
os << "[";
for (auto& x : v) {
os << x << ", ";
}
return os << "]";
}
template <typename Ostream, typename... Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p) {
return os << "{" << p.first << ", " << p.second << "}";
}
// === Debug macro ends here ===
#define f0r(i, k) for (int i = 0; i < (k); ++i)
#define fnr(i, n, k) for (int i = (n); i < (k); ++i)
#define r0f(i, k) for (int i = (k); i >= 0; --i)
#define rnf(i, n, k) for (int i = (n); i >= k; --i)
#define forl(i, l) for (auto i : l)
#define ctn(x) cout << x << '\n'
#define ctl(lst) \
{ \
for (auto& a : (lst)) cout << a << ' '; \
cout << endl; \
}
#define pb push_back
#define F first
#define S second
#define all(v) (v).begin(), (v).end()
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using pi = pair<int, int>;
using Adj = V<vi>;
using str = string;
int n, s;
pi dirs[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
V<str> grid;
bool check_cell(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n &&
(grid[x][y] == 'G' || grid[x][y] == 'M');
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> s;
grid.resize(n);
forl(&v, grid) cin >> v;
V<pi> hives;
int mechoX, mechoY, homeX, homeY;
f0r(i, n) {
f0r(j, n) {
if (grid[i][j] == 'M')
mechoX = i, mechoY = j;
else if (grid[i][j] == 'D')
homeX = i, homeY = j;
else if (grid[i][j] == 'H')
hives.pb({i, j});
}
}
dbg(hives);
dbg(mechoX);
dbg(mechoY);
dbg(homeX);
dbg(homeY);
int l = 0, r = n * n;
V<vi> mecho_time, bees_time(n, vi(n, -1));
queue<pi> q;
for (auto& [x, y] : hives) {
q.push({x, y});
bees_time[x][y] = 0;
}
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (auto [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
if (check_cell(nx, ny) && bees_time[nx][ny] == -1) {
bees_time[nx][ny] = bees_time[x][y] + 1;
q.push({nx, ny});
}
}
}
while (l <= r) {
mecho_time.assign(n, vi(n, -1));
int eat_time = (l + r) / 2;
if (bees_time[mechoX][mechoY] > eat_time) q.push({mechoX, mechoY});
mecho_time[mechoX][mechoY] = 0;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (auto [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
if (check_cell(nx, ny) && mecho_time[nx][ny] == -1) {
mecho_time[nx][ny] = mecho_time[x][y] + 1;
if (mecho_time[nx][ny] / s < (bees_time[nx][ny] - eat_time))
q.push({nx, ny});
}
}
}
bool reached = false;
for (auto [dx, dy] : dirs) {
int nx = homeX + dx, ny = homeY + dy;
reached = reached ||
check_cell(nx, ny) && (mecho_time[nx][ny] != -1) &&
(mecho_time[nx][ny] / s < (bees_time[nx][ny] - eat_time));
}
dbg(eat_time);
dbg(bees_time);
dbg(mecho_time);
if (reached)
l = eat_time + 1;
else
r = eat_time - 1;
}
ctn(l - 1);
}
