#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 805
#define mod 1000000007
char a[maxn][maxn];
int n, s, cur_bee, cur_Mecho, bee_d[maxn][maxn], Mecho_d[maxn][maxn];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
vector<pair<int, int>> pos_hive;
pair<int, int> pos_home, pos_Mecho;
queue<pair<int, int>> bee_q[2], Mecho_q[2];
bool bee_inside(int x, int y) {
return (1 <= x && x <= n && 1 <= y && y <= n && a[x][y] != 'T' && a[x][y] != 'D');
}
bool Mecho_inside(int x, int y) {
return (1 <= x && x <= n && 1 <= y && y <= n && a[x][y] != 'T' && bee_d[x][y] > 1e9);
}
bool func_Mecho(int t) {
while (Mecho_q[cur_Mecho].size()) {
auto [x, y] = Mecho_q[cur_Mecho].front();
Mecho_q[cur_Mecho].pop();
if (bee_d[x][y] < 1e9) {
continue;
}
else if (x == pos_home.first && y == pos_home.second) {
return true;
}
else if (Mecho_d[x][y] == t * s) {
Mecho_q[cur_Mecho ^ 1].push({x, y});
continue;
}
for (int i = 0; i < 4; i += 1) {
int newx = x + dx[i], newy = y + dy[i];
if (Mecho_inside(newx, newy) && Mecho_d[newx][newy] > Mecho_d[x][y] + 1) {
Mecho_d[newx][newy] = Mecho_d[x][y] + 1;
Mecho_q[cur_Mecho].push({newx, newy});
}
}
}
cur_Mecho ^= 1;
return false;
}
void func_bee(int t) {
while (bee_q[cur_bee].size()) {
auto [x, y] = bee_q[cur_bee].front();
bee_q[cur_bee].pop();
if (bee_d[x][y] == t) {
bee_q[cur_bee ^ 1].push({x, y});
continue;
}
for (int i = 0; i < 4; i += 1) {
int newx = x + dx[i], newy = y + dy[i];
if (bee_inside(newx, newy) && bee_d[newx][newy] > bee_d[x][y] + 1) {
bee_d[newx][newy] = bee_d[x][y] + 1;
bee_q[cur_bee].push({newx, newy});
}
}
}
cur_bee ^= 1;
}
bool f(int time) {
memset(bee_d, 0x3f, sizeof bee_d);
memset(Mecho_d, 0x3f, sizeof Mecho_d);
cur_bee = 0, cur_Mecho = 0;
for (auto [x, y] : pos_hive) {
bee_q[cur_bee].push({x, y});
bee_d[x][y] = 0;
}
func_bee(time);
if (bee_d[pos_Mecho.first][pos_Mecho.second] < 1e9) {
return false;
}
Mecho_d[pos_Mecho.first][pos_Mecho.second] = 0;
Mecho_q[cur_Mecho].push({pos_Mecho.first, pos_Mecho.second});
for (int t = 1; t <= n * n; t += 1) {
if (func_Mecho(t)) {
return true;
}
func_bee(time + t);
}
return false;
}
void solve() {
cin >> n >> s;
for (int i = 1; i <= n; i += 1) for (int j = 1; j <= n; j += 1) {
cin >> a[i][j];
if (a[i][j] == 'H') {
pos_hive.push_back({i, j});
}
else if (a[i][j] == 'M') {
pos_Mecho = {i, j};
}
else if (a[i][j] == 'D') {
pos_home = {i, j};
}
}
int l = -1, r = n * n + 1;
while (r - l > 1) {
int m = (l + r) / 2;
if (f(m)) {
l = m;
}
else {
r = m;
}
}
cout << l;
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int test_case = 1;
// cin >> test_case;
for (int i = 1; i <= test_case; i += 1) {
solve();
}
return 0;
}
