#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
using namespace std;
//T cay, M pos, D nha, G co, H ong
const int N = 803;
const int oo = int(1e9);
typedef pair<int, int> pii;
int lv[N][N], n, s;
bool vis[N][N];
string a[N], org[N];
queue<pii> q;
vector<pii> honey, cur, _cur, _honey;
pii st, en;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool Inside(int i, int j) {return i >= 1 && i <= n && j >= 1 && j <= n;}
int deg(int i, int j) {
int x = 0; pii nxt;
for(int k = 0; k < 4; ++k) {
nxt = mp(i + dx[k], j + dy[k]);
if(Inside(nxt.fi, nxt.se) && a[nxt.fi][nxt.se] != 'H'
&& a[nxt.fi][nxt.se] != 'T' && a[nxt.fi][nxt.se] != 'D') ++x;
}
return x;
}
bool Check(int mid) {
pii top, nxt;
while(q.size()) q.pop();
for(int i = 1; i <= n; ++i) {
a[i] = org[i];
for(int j = 1; j <= n; ++j) {
if(a[i][j] == 'H') q.push(mp(i, j));
lv[i][j] = 0;
if(a[i][j] == 'T' || a[i][j] == 'H') vis[i][j] = 1;
else vis[i][j] = 0;
}
}
if(mid) {
while(q.size()) {
top = q.front(); q.pop();
for(int i = 0; i < 4; ++i) {
nxt = mp(top.fi + dx[i], top.se + dy[i]);
if(Inside(nxt.fi, nxt.se) && !vis[nxt.fi][nxt.se] && a[nxt.fi][nxt.se] != 'D') {
if((lv[nxt.fi][nxt.se] = lv[top.fi][top.se] + 1) < mid) q.push(nxt);
a[nxt.fi][nxt.se] = 'H'; vis[nxt.fi][nxt.se] = 1;
}
}
}
}
_honey.clear();
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(a[i][j] == 'H') {
if(deg(i, j)) _honey.pb(i, j);
}
}
}
if(a[st.fi][st.se] == 'H') return 0;
_cur.clear(); _cur.pb(st); bool can = 1; vis[st.fi][st.se] = 1;
while(can) { can = 0;
for(int j = 1; j <= s; ++j) {
if(_cur.empty()) break;
cur.clear(); cur = _cur; _cur.clear(); can = 1;
for(pii p: cur) {
if(a[p.fi][p.se] == 'H') continue;
for(int k = 0; k < 4; ++k) {
nxt = mp(p.fi + dx[k], p.se + dy[k]);
if(Inside(nxt.fi, nxt.se) && !vis[nxt.fi][nxt.se]) {
vis[nxt.fi][nxt.se] = 1; _cur.pb(nxt);
if(nxt == en) return 1;
}
}
}
}
honey.clear(); honey = _honey, _honey.clear();
for(pii p: honey) {
for(int k = 0; k < 4; ++k) {
nxt = mp(p.fi + dx[k], p.se + dy[k]);
if(Inside(nxt.fi, nxt.se) && a[nxt.fi][nxt.se] != 'H' && a[nxt.fi][nxt.se] != 'T' && a[nxt.fi][nxt.se] != 'D') {
if(deg(nxt.fi, nxt.se)) _honey.pb(nxt);
vis[nxt.fi][nxt.se] = 1; a[nxt.fi][nxt.se] = 'H';
}
}
}
}
return 0;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
if(fopen("honey.inp", "r")) {
freopen("honey.inp", "r", stdin);
freopen("honey.out", "w", stdout);
}
cin >> n >> s;
for(int i = 1; i <= n; ++i) {
cin >> org[i]; org[i] = ' ' + org[i];
for(int j = 1; j <= n; ++j) {
if(org[i][j] == 'M') st = mp(i, j);
if(org[i][j] == 'D') en = mp(i, j);
}
}
int low = 0, high = int(n * n * 2), mid;
while(low <= high) {
mid = (low + high) >> 1;
if(Check(mid)) low = mid + 1;
else high = mid - 1;
}
cout << high;
}
