#include<bits/stdc++.h>
using namespace std;
#define N 805
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
struct A{
int x,y,w,cnt;
};
int dis[N][N],di[4]={1,-1,0,0},dj[4]={0,0,1,-1},ans=-1;
int n,step,sx,sy,ex,ey;
char s[N];
pair<int,int> dp[N][N];
vector<pair<int,int>> hive;
bitset<N> tree[N],vis[N];
queue<A> q;
bool sol(int mid){
int i,j,k;
for(i=1;i<=n;i++){
vis[i]=0;
for(j=1;j<=n;j++)dp[i][j]={1e9,1e9};
}
q.push({sx,sy,step,mid});
while(!q.empty()){
auto [x,y,w,cnt]=q.front();
q.pop();
if(vis[x][y])continue;
vis[x][y]=true;
for(k=0;k<4;k++){
int xx=x+di[k],yy=y+dj[k];
if(xx>0&&xx<=n&&yy>0&&yy<=n&&!vis[xx][yy]&&!tree[xx][yy]){
if(w==step&&dis[x][y]>cnt&&dis[xx][yy]>=cnt+1&&make_pair(cnt+1,1)<dp[xx][yy])q.push({xx,yy,1,cnt+1}),dp[xx][yy]=make_pair(cnt+1,1);
if(w<step&&dis[xx][yy]>=cnt&&make_pair(cnt,1)<dp[xx][yy])q.push({xx,yy,w+1,cnt}),dp[xx][yy]=make_pair(cnt,w+1);
}
}
}
return vis[ex][ey];
}
int main(){
int i,j,k,l,r,mid;
scanf("%d %d",&n,&step);
for(i=1;i<=n;i++){
scanf(" %s",s+1);
for(j=1;j<=n;j++){
if(s[j]=='T')tree[i][j]=true;
else if(s[j]=='M')sx=i,sy=j;
else if(s[j]=='D')ex=i,ey=j;
else if(s[j]=='H')hive.push_back({i,j});
dis[i][j]=1e9;
}
}
for(auto [x,y]:hive)q.push({x,y,0});
while(!q.empty()){
auto [x,y,w,cnt]=q.front();
q.pop();
if(vis[x][y])continue;
vis[x][y]=true;
dis[x][y]=w;
for(k=0;k<4;k++){
int xx=x+di[k],yy=y+dj[k];
if(xx>0&&xx<=n&&yy>0&&yy<=n&&!vis[xx][yy]&&!tree[xx][yy]&&(xx!=ex||yy!=ey))q.push({xx,yy,w+1});
}
}
l=0,r=dis[sx][sy]+1;
while(l<=r){
mid=(l+r)/2;
if(sol(mid))ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d",ans);
return 0;
}
