#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define SIZE 805
#define all(x) x.begin(), x.end()
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
int n, mxstep;
char a[SIZE][SIZE];
bool vis[SIZE][SIZE];
bool bee[SIZE][SIZE];
struct node
{
int x, y;
int s;
bool operator ==(node b)
{
return x==b.x && y==b.y;
}
};
vector<node> hive;
node start;
node endpo;
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
bool bfs(int wait)
{
queue<node> q; // bear
q.push(start);
queue<node> Q; // bee
memset(vis, 0, sizeof(vis));
memset(bee, 0, sizeof(bee));
vis[start.x][start.y]=1;
for(node t:hive)
{
bee[t.x][t.y]=1;
Q.push(t);
}
// 吃蜜时间蜜蜂围攻
while(!Q.empty() && Q.front().s<wait)
{
node w=Q.front(); Q.pop();
int i=w.x, j=w.y;
for(int k=0; k<4; k++)
{
int ni=i+dx[k];
int nj=j+dy[k];
// 不越界
if(ni<0 || ni>=n || nj<0 || nj>=n)
continue;
// 不走回头路
if(bee[ni][nj])
continue;
// 不入禁区
if(a[ni][nj]=='D' || a[ni][nj]=='T')
continue;
bee[ni][nj]=1;
Q.push({ni, nj, w.s+1});
}
}
// 原始位置已被攻占
if(bee[start.x][start.y])
return 0;
int steps=1; // 行走的次数
while(!q.empty())
{
// 小熊先走
while(!q.empty() && q.front().s<steps*mxstep)
{
node w=q.front(); q.pop();
int i=w.x, j=w.y;
if(w==endpo) return 1;
if(bee[i][j]) continue;
for(int k=0; k<4; k++)
{
int ni=i+dx[k];
int nj=j+dy[k];
// 不越界
if(ni<0 || ni>=n || nj<0 || nj>=n)
continue;
// 不被蜜蜂蛰
if(bee[ni][nj])
continue;
// 不走回头路
if(vis[ni][nj])
continue;
// 不入禁区
if(a[ni][nj]=='T')
continue;
vis[ni][nj]=1;
q.push({ni, nj, w.s+1});
}
}
// 蜜蜂后走
while(!Q.empty() && Q.front().s<wait+steps)
{
node w=Q.front(); Q.pop();
int i=w.x, j=w.y;
for(int k=0; k<4; k++)
{
int ni=i+dx[k];
int nj=j+dy[k];
// 不越界
if(ni<0 || ni>=n || nj<0 || nj>=n)
continue;
// 不走回头路
if(bee[ni][nj])
continue;
// 不入禁区
if(a[ni][nj]=='D' || a[ni][nj]=='T')
continue;
bee[ni][nj]=1;
Q.push({ni, nj, w.s+1});
}
}
steps++;
}
return 0;
}
signed main()
{
cin>>n>>mxstep;
int si, sj;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
cin>>a[i][j];
if(a[i][j]=='H')
hive.push_back({i, j, 0});
if(a[i][j]=='M')
start={i, j, 0};
if(a[i][j]=='D')
endpo={i, j, 0};
}
int l=0, r=n*n;
int ans=-1;
while(l<=r)
{
int m=(l+r)>>1;
if(bfs(m))
{
ans=m;
l=m+1;
}
else
r=m-1;
}
cout<<ans;
return 0;
}
