// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define mp make_pair
#define f first
#define s second
#define pi pair<int, int>
#ifdef LOCAL
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl '\n'
#endif
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
struct Event {
pi loc;
int dist;
};
int grid[801][801], dist_bees[801][801];
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
int S;
cin >> S;
vector<pi> hives;
pi start, end;
for (int i = 0; i < n; i++) {
string st;
cin >> st;
for (int j = 0; j < n; j++) {
if (st[j] == 'T')
grid[i][j] = -1;
else if (st[j] != 'D')
grid[i][j] = 0;
else
grid[i][j] = 1, end = {i, j};
if (st[j] == 'H') {
hives.emplace_back(i, j);
} else if (st[j] == 'M')
start = {i, j};
}
}
// let's get distance from bees first
queue<Event> bfs;
memset(dist_bees, 0x3f, sizeof dist_bees);
for (auto &[i, j] : hives) {
bfs.push({{i, j}, 0});
dist_bees[i][j] = 0;
}
while (!bfs.empty()) {
auto [i, j] = bfs.front().loc;
int dist = bfs.front().dist;
bfs.pop();
if (dist_bees[i][j] < dist)
continue;
for (int d = 0; d < 4; d++) {
int new_i = i + dx[d], new_j = j + dy[d];
if (new_i >= 0 && new_i < n && new_j >= 0 && new_j < n) {
if (grid[new_i][new_j] == 0 && dist_bees[new_i][new_j] > dist + 1) {
dist_bees[new_i][new_j] = dist + 1;
bfs.push({{new_i, new_j}, dist + 1});
}
}
}
}
// for (int i = 0; i < n; i++) {
// cout << dist_bees[i] << endl;
// }
// now mecho's turn
bfs.push({{start.f, start.s}, 0});
// just store distance w/o S factor
vector<vector<int>> mecho_dist(n, vector<int>(n, -inf));
mecho_dist[start.f][start.s] = dist_bees[start.f][start.s];
while (sz(bfs)) {
auto [i, j] = bfs.front().loc;
int dist = bfs.front().dist;
bfs.pop();
if (mecho_dist[i][j] > dist_bees[i][j] - (dist) / S)
continue;
int elapsed = (dist + 1) / S;
for (int d = 0; d < 4; d++) {
int ni = i + dx[d], nj = j + dy[d];
if (ni < 0 || ni >= n || nj < 0 || nj >= n)
continue;
// if (ni == 3 && nj == 3) {
// cout << dist + 1 << ' ' << elapsed << ' ' << dist_bees[ni][nj] << endl;
// }
int lead = min(mecho_dist[i][j], dist_bees[ni][nj] - elapsed);
if (grid[ni][nj] == 0 && mecho_dist[ni][nj] < lead && elapsed < dist_bees[ni][nj]) {
mecho_dist[ni][nj] = lead;
bfs.push({{ni, nj}, dist + 1});
}
}
}
// cout << "________" << endl;
// for (int i = 0; i < n; i++) {
// cout << mecho_dist[i] << endl;
// }
// cout << "________" << endl;
// for (int i = 0; i < n; i++) {
// cout << mecho_lead[i] << endl;
// }
int ans = -inf;
for (int d = 0; d < 4; d++) {
int ni = end.f + dx[d], nj = end.s + dy[d];
if (ni < 0 || ni >= n || nj < 0 || nj >= n)
continue;
if (grid[ni][nj] == -1 || mecho_dist[ni][nj] == inf)
continue;
ans = max(ans, mecho_dist[ni][nj] - 1);
// int elapsed = (mecho_dist[ni][nj] + S) / S;
// ans = max(ans, dist_bees[ni][nj] - elapsed);
}
if (ans < 0) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
}
// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)
