#include <bits/stdc++.h>
#define f first
#define s second
using ll = long long;
using namespace std;
const int inf = 1<<30;
int bees[800][800];
bool go[800][800];
pair<int, int> st, en;
pair<int, int> d4[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int N, S;
bool works(int t){
queue<vector<int>> bfs;
bfs.push({st.f, st.s, 0});
while(bfs.size()) {
vector<int> curr = bfs.front();
bfs.pop();
for(pair<int, int> a: d4) {
vector<int> next = {curr[0]+a.f, curr[1]+a.s, curr[2]+1};
if(next[0] >= 0 && next[0] < N && next[1] >= 0 && next[1] < N &&
go[next[0]][next[1]] && next[2]/S < bees[next[0]][next[1]]-t) {
if(next[0] == en.f && next[1] == en.s) return 1;
bfs.push(next);
}
}
}
return 0;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> S;
queue<vector<int>> hive;
for(int i = 0; i<N; i++) for(int j = 0; j<N; j++) bees[i][j] = inf;
for(int i = 0; i<N; i++) {
string c; cin >> c;
for(int j = 0; j<N; j++) {
go[i][j] = c[j] != 'T';
if(c[j] == 'M') st = {i, j};
if(c[j] == 'D') en = {i, j};
if(c[j] == 'H') {
hive.push({i, j});
bees[i][j] = 0;
}
}
}
while(hive.size()) {
vector<int> curr = hive.front();
hive.pop();
int c = bees[curr[0]][curr[1]];
for(pair<int, int> a: d4) {
vector<int> next = {curr[0]+a.f, curr[1]+a.s};
if(next[0] >= 0 && next[1] >= 0 && next[0] < N && next[1] < N &&
go[next[0]][next[1]] && bees[next[0]][next[1]] == inf && (next[0] != en.f || next[1] != en.s)) {
bees[next[0]][next[1]] = c+1;
hive.push(next);
}
}
}
int lo = -1, hi = bees[st.f][st.s]+1;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (works(mid)) lo = mid;
else hi = mid - 1;
}
cout << lo;
}
