// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using pii = pair<int,int>;
#define INF 2000000000
int x[4] = {1,-1,0,0};
int y[4] = {0,0,1,-1};
int main() {
int N, S; cin>>N>>S;
int arr[N][N];
unordered_map<char, int> lets;
lets['T']=1; lets['G']=2;lets['M']=3; lets['D']=4, lets['H']=5;
//G, M, D, H
queue<pii> hives;
pii start;
pii end;
int dist[N][N];
bool visit[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
visit[i][j] = false;
dist[i][j] = -1;
}
}
for (int i=0; i<N; i++){
for (int j=0; j<N; j++){
char let; cin>>let;
int num = lets[let];
arr[i][j]=num;
if (num==5){hives.push({i, j}); dist[i][j]=0;visit[i][j]=true;}
if (num==3){start = {i, j};}
if (num==4){end = {i, j};}
}
}
while (!hives.empty()) {
pii loc = hives.front();
hives.pop();
for (int i = 0; i < 4; i++) {
int nf = loc.F + x[i];
int ns = loc.S + y[i];
if (nf < 0 || nf >= N || ns < 0 || ns >= N) {continue;}
if (visit[nf][ns]||(arr[nf][ns] !=2 && arr[nf][ns]!=3)) {continue;}
visit[nf][ns] = true;
dist[nf][ns] = dist[loc.F][loc.S] + 1;
hives.push({nf, ns});
}
}
dist[end.F][end.S]=INF;
int min = -1;
int max = dist[start.F][start.S];
while (max>min+1){
int mid = (max+min)/2;
queue<std::pair<int, pii>> order;
bool visit[N][N];
for (int i=0; i<N; i++){for(int j = 0; j<N; j++){visit[i][j]=false;}}
order.push({0, start});
visit[start.F][start.S]=true;
while (!order.empty()){
pii loc = order.front().second;
int distance = order.front().first;
order.pop();
for (int i=0; i<4; i++){
int nf = loc.F + x[i];
int ns = loc.S + y[i];
if (nf < 0 || nf >= N || ns < 0 || ns >= N) {continue;}
if (visit[nf][ns]||arr[nf][ns] == 1||arr[nf][ns]==5) {continue;}
if ((distance+1)/S + mid >= dist[nf][ns]){continue;}
visit[nf][ns] = true;
order.push({distance + 1, {nf, ns}});
}
}
if (visit[end.F][end.S]){min = mid;}
else{max = mid;}
}
cout<<min<<endl;
}
