#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int bulan=100000;
const int dx[]={0, 0, -1, 1};
const int dy[]={-1, 1, 0, 0};
int n, s, ok;
int viz[805][805], blocked[805][805], xs, ys, ye, xe, viz2[805][805];
char mat[805][805];
vector <pair <int, int>> initial, trees;
queue <pair <int, int>> coadab[bulan+5];
queue <vector <int>> coada[bulan+5];
bool ismat (int i, int j)
{
return i>=1 && j>=1 && i<=n && j<=n;
}
void moveBees (int time)
{
while (!coadab[time].empty())
{
int x=coadab[time].front().first;
int y=coadab[time].front().second;
coadab[time].pop();
blocked[x][y]=1;
for (int i=0;i<=3;i++)
{
int inou=dx[i]+x;
int jnou=dy[i]+y;
if (ismat (inou, jnou) && !viz[inou][jnou] && (mat[inou][jnou]=='G' || mat[inou][jnou]=='M'))
{
viz[inou][jnou]=1;
coadab[time+1].push ({inou, jnou});
}
}
}
}
void moveBear (int time)
{
while (!coada[time].empty())
{
int x=coada[time].front()[0];
int y=coada[time].front()[1];
int step=coada[time].front()[2];
coada[time].pop();
if (blocked[x][y])
continue;
if (x==xe && y==ye)
ok=1;
for (int i=0;i<=3;i++)
{
int inou=dx[i]+x;
int jnou=dy[i]+y;
if (ismat (inou, jnou) && !viz2[inou][jnou] && !blocked[inou][jnou] && (mat[inou][jnou]=='G' || mat[inou][jnou]=='D'))
{
viz2[inou][jnou]=1;
if (step==s-1)
{
coada[time+1].push ({inou, jnou, 0});
}
else coada[time].push ({inou, jnou, step+1});
}
}
}
}
bool check (int val)
{
ok=0;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
viz[i][j]=0;
viz2[i][j]=0;
blocked[i][j]=0;
}
}
for (int i=0;i<=bulan+1;i++)
{
while (!coada[i].empty())
{
coada[i].pop();
}
while (!coadab[i].empty())
{
coadab[i].pop();
}
}
coada[val+1].push ({xs, ys, 0});
viz2[xs][ys]=1;
for (auto tree : trees)
{
blocked[tree.first][tree.second]=1;
viz[tree.first][tree.second]=1;
}
for (auto poz : initial)
{
viz[poz.first][poz.second]=1;
coadab[0].push ({poz.first, poz.second});
}
moveBees (0);
for (int crt_time=1;;crt_time++)
{
if (crt_time>val && coada[crt_time].empty())
return 0;
if (crt_time>val) moveBear (crt_time);
if (ok)
{
break;
}
moveBees (crt_time);
}
return 1;
}
int main ()
{
cin >> n >> s;
for (int i=1;i<=n;i++)
{
string s;
cin >> s;
for (int j=1;j<=n;j++)
{
mat[i][j]=s[j-1];
if (mat[i][j]=='T')
{
trees.push_back ({i, j});
}
if (mat[i][j]=='H')
{
initial.push_back ({i, j});
}
if (mat[i][j]=='M')
{
xs=i;
ys=j;
}
if (mat[i][j]=='D')
{
ye=j;
xe=i;
}
}
}
int st=0, dr=bulan+1, poz=-1;
while (st<=dr)
{
int mij = (st+dr) >> 1;
if (check (mij))
{
st=mij+1;
poz=mij;
}
else dr=mij-1;
}
cout << poz;
return 0;
}
