#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <utility>
#include <map>
#define ll long long int
const ll mod=1e9+7;
using namespace std;
/*
? Did I test edge cases? (Empty, min/max, 1-element, same elements, etc.)
? Did I reread the full prompt to recheck constraints?
? Does my code handle ties, negatives, zeroes, or duplicates?
? Am I brute-forcing something unnecessarily?
? Am I assuming things not in the problem?
Have I defined all state variables explicitly?
Do I know what each transition costs?
Have I written 2 edge-case scenarios by hand?
*/
queue<pair<int,int> > prep;
queue<int> clos;
int closest[800][800];
int d;
int n;
void bfs1(int i,int j,int visited2[][800],int c,int n,string a[])
{
prep.pop();
clos.pop();
if(a[i][j]=='H')
closest[i][j]=0;
else
closest[i][j]=c;
if(i!=0)
if(visited2[i-1][j]!=1)
{
visited2[i-1][j]=1;
prep.push(make_pair(i-1,j));
clos.push(c+1);
}
if(i!=n-1)
if(visited2[i+1][j]!=1)
{
visited2[i+1][j]=1;
prep.push(make_pair(i+1,j));
clos.push(c+1);
}
if(j!=0)
if(visited2[i][j-1]!=1)
{
visited2[i][j-1]=1;
prep.push(make_pair(i,j-1));
clos.push(c+1);
}
if(j!=n-1)
if(visited2[i][j+1]!=1)
{
visited2[i][j+1]=1;
prep.push(make_pair(i,j+1));
clos.push(c+1);
}
if(prep.size())
bfs1(prep.front().first,prep.front().second,visited2,clos.front(),n,a);
}
int r(int steps,int d)
{
if(steps%d)
return steps/d+1;
else
return steps/d;
}
/*
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT*/
int bfs(string a[],int visited[][800],int i,int j,queue<int>& time,queue<pair<int,int> >& order,int ext)
{
order.pop();
if(a[i][j]=='D')
{
return 1;
}
if(ext+r(time.front(),d)>=closest[i][j] or a[i][j]=='H' or a[i][j]=='T')
{
if(order.size())
return bfs(a,visited,order.front().first,order.front().second,time,order,ext);
return 0;
}
if(i!=n-1)
if(visited[i+1][j]!=1)
{
visited[i+1][j]=1;
time.push(time.front()+1);
order.push(make_pair(i+1,j));
}
if(i!=0)
if(visited[i-1][j]!=1)
{
visited[i-1][j]=1;
time.push(time.front()+1);
order.push(make_pair(i-1,j));
}
if(j!=n-1)
if(visited[i][j+1]!=1)
{
visited[i][j+1]=1;
time.push(time.front()+1);
order.push(make_pair(i,j+1));
}
if(j!=0)
if(visited[i][j-1]!=1)
{
visited[i][j-1]=1;
time.push(time.front()+1);
order.push(make_pair(i,j-1));
}
time.pop();
if(time.size())
return bfs(a,visited,order.front().first,order.front().second,time,order,ext);
return 0;
}
int main(){
//cin.tie(0)->sync_with_stdio(false);
cin>>n>>d;
string a[n];
int visited2[800][800],start1,start2;
for(int i=0;i<n;i++)
{
cin>>a[i];
for(int j=0;j<n;j++)
{
if(a[i][j]=='H')
{
prep.push(make_pair(i,j));
clos.push(0);
visited2[i][j]=1;
}
else if(a[i][j]=='M')
{
start1=i;
start2=j;
}
}
}
bfs1(prep.front().first,prep.front().second,visited2,0,n,a);
int l=0,r=2*n,ans=-1;
while(l<=r)
{
int mid=l;
queue<pair<int,int> > order;
order.push(make_pair(start1,start2));
int visited[800][800];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
visited[i][j]=0;
queue<int> time;
time.push(0);
if(bfs(a,visited,start1,start2,time,order,mid))
{
ans=mid;
}
l++;
}
cout<<ans;
return 0;
}
