#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<ll, ll>
#define ppll pair< pair<long long, long long>, long long >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
const ll DIM = 800 + 7;
const ll INF = 1e18;
const ll mod = 998244353;
const ll maxlog = 20;
const ll bsize = 350;
char c[DIM][DIM];
ll dist[DIM][DIM], dist2[DIM][DIM];
vector<pll> bees;
ll sti, stj, fi, fj;
ll n, s;
bool can (ll x) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
dist[i][j] = INF;
}
}
queue<pll> q;
for (auto [i, j] : bees) {
q.push({i, j});
dist[i][j] = 0;
}
while (!q.empty()) {
auto [i, j] = q.front(); q.pop();
if (dist[i][j] == x) continue;
if (i>1 && c[i-1][j]!='T' && c[i-1][j]!='D' && dist[i-1][j] == INF) {
dist[i-1][j] = dist[i][j] + 1;
q.push({i-1, j});
}
if (i<n && c[i+1][j]!='T' && c[i+1][j]!='D' && dist[i+1][j] == INF) {
dist[i+1][j] = dist[i][j] + 1;
q.push({i+1, j});
}
if (j>1 && c[i][j-1]!='T' && c[i][j-1]!='D' && dist[i][j-1] == INF) {
dist[i][j-1] = dist[i][j] + 1;
q.push({i, j-1});
}
if (j<n && c[i][j+1]!='T' && c[i][j+1]!='D' && dist[i][j+1] == INF) {
dist[i][j+1] = dist[i][j] + 1;
q.push({i, j+1});
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (dist[i][j] != INF) {
q.push({i, j});
dist[i][j] = 0;
}
}
}
while (!q.empty()) {
auto [i, j] = q.front(); q.pop();
if (i>1 && c[i-1][j]!='T' && c[i-1][j]!='D' && dist[i-1][j] == INF) {
dist[i-1][j] = dist[i][j] + 1;
q.push({i-1, j});
}
if (i<n && c[i+1][j]!='T' && c[i+1][j]!='D' && dist[i+1][j] == INF) {
dist[i+1][j] = dist[i][j] + 1;
q.push({i+1, j});
}
if (j>1 && c[i][j-1]!='T' && c[i][j-1]!='D' && dist[i][j-1] == INF) {
dist[i][j-1] = dist[i][j] + 1;
q.push({i, j-1});
}
if (j<n && c[i][j+1]!='T' && c[i][j+1]!='D' && dist[i][j+1] == INF) {
dist[i][j+1] = dist[i][j] + 1;
q.push({i, j+1});
}
}
if (dist[sti][stj] <= x) return 0;
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
dist2[i][j] = INF;
}
}
dist2[sti][stj] = 0;
q.push({sti, stj});
while (!q.empty()) {
auto [i, j] = q.front(); q.pop();
if (i == fi && j == fj) break;
vector< pair<pll, ll> > vec;
vec.pb({{i, j}, 0});
ll p = 0;
while (p < vec.size()) {
auto [coord, step] = vec[p];
p++;
ll i2 = coord.ff, j2 = coord.ss;
//cout << "// " << i2 << " " << j2 << endl;
if (step == s) continue;
if (i2>1 && c[i2-1][j2]!='T' && dist2[i2-1][j2] == INF && (dist2[i][j]+1) <= dist[i2-1][j2]) {
dist2[i2-1][j2] = dist2[i][j] + 1;
vec.pb({{i2-1, j2}, step+1});
q.push({i2-1, j2});
}
if (i2<n && c[i2+1][j2]!='T' && dist2[i2+1][j2] == INF && (dist2[i][j]+1) <= dist[i2+1][j2]) {
dist2[i2+1][j2] = dist2[i][j] + 1;
vec.pb({{i2+1, j2}, step+1});
q.push({i2+1, j2});
}
if (j2>1 && c[i2][j2-1]!='T' && dist2[i2][j2-1] == INF && (dist2[i][j]+1) <= dist[i2][j2-1]) {
dist2[i2][j2-1] = dist2[i][j] + 1;
vec.pb({{i2, j2-1}, step+1});
q.push({i2, j2-1});
}
if (j2<n && c[i2][j2+1]!='T' && dist2[i2][j2+1] == INF && (dist2[i][j]+1) <= dist[i2][j2+1]) {
dist2[i2][j2+1] = dist2[i][j] + 1;
vec.pb({{i2, j2+1}, step+1});
q.push({i2, j2+1});
}
}
}
/*for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (dist[i][j] == INF) cout << "- ";
else cout << dist[i][j] << " ";
}
cout << endl;
}
cout << endl;
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (dist2[i][j] == INF) cout << "- ";
else cout << dist2[i][j] << " ";
}
cout << endl;
}
cout << endl;*/
return (dist2[fi][fj] != INF);
}
void solve() {
cin >> n >> s;
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
dist[i][j] = INF;
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
cin >> c[i][j];
if (c[i][j] == 'M') sti = i, stj = j;
else if (c[i][j] == 'D') fi = i, fj = j;
else if (c[i][j] == 'H') {
bees.pb({i, j});
dist[i][j] = 0;
}
}
}
ll L = 0, R = n;
while (L < R) {
ll mid = (L + R + 1) >> 1;
//cout << "/ " << mid << endl;
//cout << can(mid) << endl;
if (can(mid)) L = mid;
else R = mid-1;
}
if (can(L)) cout << L << endl;
else cout << -1 << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//freopen("atlarge.in", "r", stdin);
//freopen("atlarge.out", "w", stdout);
int ntest = 1;
//cin >> ntest;
while (ntest--) {
solve();
}
return 0;
}
;
