#include<bits/stdc++.h>
using namespace std;
#define in insert
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define Endl "\n"
#define ENDL "\n"
#define fi first
#define se second
#define be begin()
#define en end()
#define pb push_back
#define mpa make_pair
typedef long long ll;
typedef long double ld;
const int MOD=1e9+7;
const int MAX=2e5+1;
int n,s;
string arr[802][802];
bool vist[802][802];
int mechoDist[802][802];
int BeesDist[802][802];
pair<int,int> mecho;
pair<int,int> home;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
bool valid (int x,int y){
return x>=1&&x<=n&&y>=1&&y<=n&&!vist[x][y]&&arr[x][y]!="T";
}
bool check =false;
void bfs (int i,int j ,int val){
vist[i][j]=true;
queue<pair<int,int>>q;
q.push(mpa(i,j));
while (!q.empty()){
auto p =q.front();
int x = p.fi;
int y = p.se;
q.pop();
if(x==home.fi&&y==home.se)check=true;
if(val+mechoDist[x][y]>=BeesDist[x][y])continue;
for (int w=0;w<4;w++){
int nx = x+dx[w];
int ny = y+dy[w];
if(valid(nx,ny)){
vist[nx][ny]=true;
q.push(mpa(nx,ny));
}
}
}
}
int main(){
fastio
//freopen("11.in","r",stdin);
//freopen("cl.out","w",stdout);
cin>>n>>s;
for (int i=1;i<=n;i++){
string s;
cin>>s;
for (int j=1;j<=n;j++){
arr[i][j]=s[j-1];
if(arr[i][j]=="M")mecho=mpa(i,j);
else if (arr[i][j]=="D")home = mpa(i,j);
}
}
queue <pair<int,int>> q;
q.push(mecho);
vist[mecho.fi][mecho.se]=true;
while(!q.empty()){
auto p = q.front();
int x = p.fi;
int y = p.se;
q.pop();
for (int i=0;i<4;i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(valid(nx,ny)&&arr[nx][ny]!="H"){
mechoDist[nx][ny]=mechoDist[x][y]+1;
vist[nx][ny]=true;
q.push(mpa(nx,ny));
}
}
}
for (int i=1;i<=n;i++)for(int j=1;j<=n;j++){
mechoDist[i][j]=mechoDist[i][j]/s;
vist[i][j]=false;
}
for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){
if(arr[i][j]=="H"){
q.push(mpa(i,j));
vist[i][j]=true;
}
}
while(!q.empty()){
auto p = q.front();
int x = p.fi;
int y = p.se;
q.pop();
for (int i=0;i<4;i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(valid(nx,ny)&&arr[nx][ny]!="D"&&arr[nx][ny]!="H"){
BeesDist[nx][ny]=BeesDist[x][y]+1;
vist[nx][ny]=true;
q.push(mpa(nx,ny));
}
}
}
/*cout<<endl<<endl;
for(int i=1;i<=n;i++){for (int j=1;j<=n;j++){
if(arr[i][j]=="G")
cout<<mechoDist[i][j];
else cout<<arr[i][j];
}
cout<<endl;
}
cout<<endl<<endl;
for(int i=1;i<=n;i++){for (int j=1;j<=n;j++){
cout<<BeesDist[i][j];
}
cout<<endl;
}*/
int l=0;
int r = 1e9;
int ans =-1;
while (l<=r){
int mid = (l+r)/2;
for (int i=1;i<=n;i++)for(int j=1;j<=n;j++){
vist[i][j]=false;
}
check=false;
bfs(mecho.fi,mecho.se,mid);
if(check){
l=mid+1;
ans = mid;
} else {
r=mid-1;
}
}
cout<<ans;
return 0;
}
unsigned long long power(unsigned long long x,
ll y, ll p)
{
unsigned long long res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
unsigned long long modInverse(unsigned long long n,
ll p)
{
return power(n, p - 2, p);
}
