// ============================================================================ //
// || || //
// || || //
//*|| // Jigyasu's Template for cpp // || //
// ||--------------------------Expert till July 2025-------------------------|| //
// || || //
// || || //
// ============================================================================ //
#include <bits/stdc++.h>
using namespace std;
#define fast_io cin.sync_with_stdio(false); cin.tie(0); cout.tie(0)
// #define cerr if(false)cerr
#define int long long
#define ll long long
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(x) (int)(x).size()
#define MOD 1000000007
#define INF (int)1e16
#define endl "\n"
#define sp " "
// #define endl endl; cout.flush();
#define input(a, n) vi a(n); for(int i = 0; i < n; i++) cin >> a[i];
#define yes cout << "YES" << endl; return;
#define no cout << "NO" << endl; return;
#define vi vector<int>
#define vvi vector<vector<int> >
#define ai(zzz) array<int, zzz>
#define pii pair<int, int>
// #define f(i, a, b) for (int i = a; i < b; i++)
// #define fr(i, a, b) for (int i = a; i > b; i--)
//?--------------------------------------------------------------------------------------------------------------------
template <typename T> std::ostream &operator<<(std::ostream &stream, const vector<T> &vec) {for (size_t i = 0; i < vec.size(); i++) { stream << vec[i]; if (i != vec.size() - 1) stream << ' '; }; return stream; } template <typename T> std::istream &operator>>(std::istream &stream, vector<T> &vec) {for (T &x : vec) stream >> x; return stream; } template <typename T> std::istream &operator>>(std::istream &stream, array<T, 2> &arr) {stream >> arr[0] >> arr[1]; return stream; } template <typename T> std::ostream &operator<<(std::ostream &stream, const array<T, 2> &arr) {stream << '(' << arr[0] << ", " << arr[1] << ')'; return stream; } template <typename T, typename U> std::ostream &operator<<(std::ostream &stream, const pair<T, U> &pr) {stream << pr.first << ' ' << pr.second; return stream; } template <typename T, typename U> std::istream &operator>>(std::istream &stream, pair<T, U> &pr) {stream >> pr.first >> pr.second; return stream; } template <typename A, typename B> string to_string(pair<A, B> p); template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p); template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p); string to_string(const string &s) { return '"' + s + '"'; } string to_string(char c) {string s; s += c; return s; } string to_string(const char *s) { return to_string((string)s); } string to_string(bool b) { return (b ? "1" : "0"); } string to_string(vector<bool> v) {bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) {if (!first) {res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template <size_t N> string to_string(bitset<N> v) {string res = ""; for (size_t i = 0; i < N; i++) {res += static_cast<char>('0' + v[i]); } return res; } template <typename A> string to_string(A v) {bool first = true; string res = "{"; for (const auto &x : v) {if (!first) {res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cout << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cout << " " << to_string(H); debug_out(T...); }
//* Debuggers
#define debug(x) cout << #x << " = " << x << endl;
template<typename T>
void print_container(const T& container) {
for (auto it = container.begin(); it != container.end(); ++it) {
cout << *it;
if (next(it) != container.end()) cout << " ";
}
cout << endl;
}
#define print(x) print_container(x);
//?--------------------------------------------------------------------------------------------------------------------
//* Sieve of Eratosthenes for primes
vector<int> sieve(int n) {
vi st;
// map<int, set<int> >hey_mp;
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (is_prime[i]) {
// hey_mp[i].insert(i);
for (int j = i * i; j <= n; j += i) {
// if (is_prime[j]) hey_mp[i].push_back(j);
is_prime[j] = false;
// hey_mp[i].insert(j);
}
}
}
// return hey_mp;
for (int i = 0; i <= n; i++) {
if (is_prime[i]) {
st.pb(i);
}
}
return st;
}
//?--------------------------------------------------------------------------------------------------------------------
//* Modular Multiplication
ll mod_mul(ll a, ll b) {return ((a % MOD) * (b % MOD)) % MOD;}
//* Binary Exponentiation
ll binpow(ll a, ll b, ll m = MOD) {
ll res = 1;
a %= m;
while (b) {
if (b & 1ll) res = res * a % m;
a = mod_mul(a, a);
b >>= 1ll;
}
return res;
}
//* Modular Addition
ll mod_add(ll a, ll b) {return ((a % MOD) + (b % MOD)) % MOD;}
//* Modular Subtraction
ll mod_sub(ll a, ll b) {return ((a % MOD) - (b % MOD) + MOD) % MOD;}
//* Modular Division (using Modular Inverse)
ll mod_inv(ll a, ll m = MOD) {return binpow(a, m - 2, m);} // Fermat's Little Theorem
ll mod_div(ll a, ll b) {return mod_mul(a, mod_inv(b));}
//?--------------------------------------------------------------------------------------------------------------------
//?--------------------------------------------------------------------------------------------------------------------
int n, s, sx = -1, sy = -1, ex = -1, ey = -1;
vector<vector<char>>grid;
vector<vector<int>>bee_time;
bool is_valid1(int i, int j, int time) {
if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] == 'T' || (time / s) >= bee_time[i][j]) return false;
return true;
}
bool bfs(int time_eaten) {
if (bee_time[sx][sy] <= (time_eaten)) return false;
queue<ai(2)>q;
vector<vector<int> >dist(n, vector<int>(n, INF));
q.push({sx, sy});
dist[sx][sy] = time_eaten * s;
while (!q.empty()) {
auto [i, j] = q.front(); q.pop();
int t = dist[i][j] + 1;
if (is_valid1(i-1, j, t) && dist[i-1][j] == INF) {
q.push({i-1, j});
dist[i-1][j] = t;
}
if (is_valid1(i+1, j, t) && dist[i+1][j] == INF) {
q.push({i+1, j});
dist[i+1][j] = t;
}
if (is_valid1(i, j-1, t) && dist[i][j-1] == INF) {
q.push({i, j-1});
dist[i][j-1] = t;
}
if (is_valid1(i, j+1, t) && dist[i][j+1] == INF) {
q.push({i, j+1});
dist[i][j+1] = t;
}
}
return dist[ex][ey] != INF;
}
bool is_valid(int i, int j) {
if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] == 'T' || grid[i][j] == 'D' || bee_time[i][j] != INF) return false;
return true;
}
void Solve() {
cin >> n >> s;
grid.resize(n, vector<char>(n));
bee_time.resize(n, vector<int>(n, INF));
queue<ai(2)>q;
for (int i = 0; i < n; i++) {
string str; cin >> str;
for (int j = 0; j < n; j++) {
grid[i][j] = str[j];
if (grid[i][j] == 'M') {
sx = i; sy = j;
}
else if (grid[i][j] == 'D') {
ex = i; ey = j;
}
else if (grid[i][j] == 'H') {
bee_time[i][j] = 0;
q.push({i, j});
}
}
}
while (!q.empty()) {
auto [i, j] = q.front(); q.pop();
if (is_valid(i-1, j)) {
bee_time[i-1][j] = bee_time[i][j] + 1;
q.push({i-1, j});
}
if (is_valid(i+1, j)) {
bee_time[i+1][j] = bee_time[i][j] + 1;
q.push({i+1, j});
}
if (is_valid(i, j-1)) {
bee_time[i][j-1] = bee_time[i][j] + 1;
q.push({i, j-1});
}
if (is_valid(i, j+1)) {
bee_time[i][j+1] = bee_time[i][j] + 1;
q.push({i, j+1});
}
}
int l = 0, r = 1e9, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (bfs(mid)) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << ans << endl;
}
int32_t main() {
#ifndef ONLINE_JUDGE
auto start = chrono::high_resolution_clock::now(); // Start timer
// freopen("atlarge.in", "r", stdin);
// freopen("atlarge.out", "w", stdout);
#endif
fast_io;
int tt = 1;
// cin >> tt;
while (tt--) Solve();
#ifndef ONLINE_JUDGE
auto end = chrono::high_resolution_clock::now(); // End timer
chrono::duration<double, milli> duration = end - start;
cerr << "Time: " << duration.count() << " ms" << endl;
#endif
}
