#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("fast-math")
#define ll int16_t
#define ld long double
#define vi vector<ll>
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
const int mod = 1e9+7;
void _p(ll a){cout<<a<<endl;}
void _p(string a){cout<<a<<endl;}
void _p(ld a) {cout<<a<<endl;}
template <class T>
void _p(vector<T> a){for(T val:a)cout<<val<<" ";cout<<endl;}
#define debug(x) cout<<#x<<" -> ";_p(x)
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
vector<pr> move8 = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
vector<pr> move4 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<pr> move2 = {{0, 1}, {1, 0}};
void solution();
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solution();
return 0;
}
pr operator+(pr p1, pr p2) {
pr ans = {p1.ff +p2.ff, p1.ss+p2.ss};
return ans;
}
const int MAXN = 805;
const int inf = 1e9;
char A[MAXN][MAXN];
int arr[MAXN][MAXN];
ll n, s;
pr start, destination;
vector<pr> H;
bool vis[MAXN][MAXN];
bool correct(pr cords) {
return cords.ff <= n && cords.ff >= 1 &&
cords.ss <= n && cords.ss >= 1 &&
A[cords.ff][cords.ss] != 'T';
}
void calculateArrival() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
arr[i][j] = inf;
}
}
queue<pr> q;
pr wa = {-1, -1};
ll tm = 0;
for (auto val : H) q.push(val);
q.push(wa);
while (!q.empty()) {
pr e = q.front(); q.pop();
if (e == wa) {
if (q.size() > 0) q.push(wa);
tm++;
continue;
}
if (arr[e.ff][e.ss] < tm) continue;
arr[e.ff][e.ss] = tm;
for (auto D : move4) {
pr nkw = D + e;
if (!correct(nkw) || arr[nkw.ff][nkw.ss] != inf ||
A[nkw.ff][nkw.ss] == 'D') continue;
q.push(nkw);
}
}
}
// bool isValid(ll tm) {
// if (tm >= arr[start.ff][start.ss]) return false;
// queue<pair<pr, ll>> q;
// q.push({start, 0});
// while (!q.empty()) {
// auto [e, t] = q.front(); q.pop();
// if (vis[e.ff][e.ss] ||
// ceil((ld)t/s)+ tm > arr[e.ff][e.ss]) continue;
// vis[e.ff][e.ss] = true;
// if (e == destination) return true;
// for (auto D : move4) {
// pr nkw = e+D;
// if (!correct(nkw) || vis[nkw.ff][nkw.ss]) continue;
// q.push({nkw, t+1});
// }
// }
// return false;
// }
bool isValid(int waiting_time) {
// Check if bees reach start before Mecho can leave
if (waiting_time >= arr[start.ff][start.ss]) {
return false;
}
queue<pair<pr, int>> q;
q.push({start, 0});
vis[start.ff][start.ss] = true;
while (!q.empty()) {
pr pos = q.front().first;
int steps = q.front().second;
q.pop();
if (pos == destination) {
return true;
}
for (auto D : move4) {
pr next_pos = pos + D;
int next_steps = steps + 1;
// Check bounds and trees
if (next_pos.ff < 1 || next_pos.ff > n || next_pos.ss < 1 || next_pos.ss > n) {
continue;
}
if (A[next_pos.ff][next_pos.ss] == 'T' || vis[next_pos.ff][next_pos.ss]) {
continue;
}
// Calculate time - Mecho finishes next_steps at this minute
int mecho_time = waiting_time + (next_steps + s - 1) / s;
// Can only visit if Mecho arrives before or at same time as bees
if (mecho_time > arr[next_pos.ff][next_pos.ss]) {
continue;
}
vis[next_pos.ff][next_pos.ss] = true;
q.push({next_pos, next_steps});
}
}
return false;
}
void solution() {
cin >> n >> s;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> A[i][j];
if (A[i][j] == 'M') start = {i, j};
if (A[i][j] == 'D') destination = {i, j};
if (A[i][j] == 'H') H.push_back({i, j});
}
}
calculateArrival();
// {
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// cout << arr[i][j] << " ";
// }
// cout << endl;
// }
// }
ll p = 0, q = 1e7;
ll ans = -1;
while (p <= q) {
ll mid = (p + q)/2;
if (isValid(mid)) {
ans = mid;
p = mid+1;
}else q = mid-1;
memset(vis, 0, sizeof(vis));
}
cout << ans << endl;
}
