// Author: Teoman Ata Korkmaz
#include <bits/stdc++.h>
#define int int32_t
using namespace std;
constexpr int N=808;
///////////////////////////////////////////////////////////
int n,k,t[N][N];
bool vis[N][N];
pair<int,int> startpoint;
string s[N];
inline void bfs(){
memset(t,-1,sizeof(t));
queue<pair<int,int>> q;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(s[i][j]=='H'){
q.push({i,j});
t[i][j]=0;
}
}
}
while(q.size()){
auto [i,j]=q.front();q.pop();
// cerr<<"i,j: "<<i<<" "<<j<<endl;
if(i>0 && t[i-1][j]==-1 && s[i-1][j]=='G') t[i-1][j]=t[i][j]+1, q.push({i-1,j});
if(i<n-1 && t[i+1][j]==-1 && s[i-1][j]=='G') t[i+1][j]=t[i][j]+1, q.push({i+1,j});
if(j>0 && t[i][j-1]==-1 && s[i-1][j]=='G') t[i][j-1]=t[i][j]+1, q.push({i,j-1});
if(j<n-1 && t[i][j+1]==-1 && s[i-1][j]=='G') t[i][j+1]=t[i][j]+1, q.push({i,j+1});
}
}
inline bool f(int x){
// cerr<<"f: "<<x<<endl;
memset(vis,0,sizeof(vis));
queue<pair<int,pair<int,int>>> q;
q.push({0,startpoint});
while(q.size()){
auto [d,_]=q.front();
auto [i,j]=_;q.pop();
// cerr<<"d,i,j: "<<d<<" "<<i<<" "<<j<<endl;
if(vis[i][j])continue;
if(x+d/3>=t[i][j])continue;
if(s[i][j]=='T')continue;
if(s[i][j]=='D')return true;
vis[i][j]=true;
if(i>0 ) q.push({d+1,{i-1,j}});
if(i<n-1) q.push({d+1,{i+1,j}});
if(j>0 ) q.push({d+1,{i,j-1}});
if(j<n-1) q.push({d+1,{i,j+1}});
}
return false;
}
signed main(void){
cin>>n>>k;
for(int i=0;i<n;i++)cin>>s[i];
for(int i=0;i<n;i++){
bool flag=false;
for(int j=0;j<n;j++){
if(s[i][j]=='M'){
startpoint={i,j};
s[i][j]='G';
flag=true;
break;
}
}
if(flag)break;
}
bfs();
int l=0,r=1e5;
while(l<r){
int m=(l+r)>>1;
if(f(m))l=m+1;
else r=m;
}
cout<<l-1<<endl;
}
