#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define nl '\n'
using ll = long long;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, S; cin >> N >> S;
vector<vector<int>> grid(N, vector<int> (N));
char c;
pair<int, int> Mecho, Home;
vector<pair<int, int>> hives;
for (int a=0; a<N; a++) {
for (int b=0; b<N; b++) {
cin >> c;
if (c == 'T') grid[a][b] = 0;
if (c == 'G') grid[a][b] = 1;
if (c == 'M') {
grid[a][b] = 1;
Mecho = {a, b};
}
if (c == 'D') {
grid[a][b] = 2;
Home = {a, b};
}
if (c == 'H') {
grid[a][b] = 1;
hives.pb({a, b});
}
}
}
ll a=0, b = 1e8;
while (a <= b) {
ll minutes = (a+b)/2;
vector<vector<bool>> used(N, vector<bool> (N));
vector<vector<bool>> UsedMecho(N, vector<bool> (N));
deque<pair<bool, queue<pair<int, int>>>> q;
//0 = bees
//1 = Mecho
for (auto hive: hives) {
queue<pair<int, int>> myQ;
myQ.push({hive.first, hive.second});
q.push_front({0, myQ});
used[hive.first][hive.second] = 1;
UsedMecho[hive.first][hive.second] = 1;
}
bool MechoIn = 0;
vector<pair<int, int>> moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
//destra, sinistra, sotto, sopra
vector<vector<int>> dist(N, vector<int> (N)), distBee(N, vector<int> (N));
while(q.size() != 0) {
auto t = q.front(); q.pop_front();
bool isMecho; queue<pair<int, int>> myQ; tie(isMecho, myQ) = t;
queue<pair<int, int>> last;
if (isMecho) {
if (myQ.size() == 0) break;
queue<pair<int, int>> Mechos;
while(!myQ.empty()) {
int x = myQ.front().first, y = myQ.front().second; myQ.pop();
Mechos.push({x, y});
dist[x][y] = 0;
}
while(!Mechos.empty()) {
int x = Mechos.front().first, y = Mechos.front().second; Mechos.pop();
if (dist[x][y] == S) {
// cout << x << " " << y << nl;
last.push({x, y});
continue;
}
for (auto move: moves) {
int nx = x + move.first, ny = y + move.second;
//Siamo Mecho
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (grid[nx][ny] == 0 || UsedMecho[nx][ny] || used[nx][ny]) continue;
UsedMecho[nx][ny] = 1;
dist[nx][ny] = dist[x][y] + 1;
Mechos.push({nx, ny});
}
}
if (!last.empty()) q.push_back({1, last});
} else {
while(!myQ.empty()) {
int x = myQ.front().first, y = myQ.front().second; myQ.pop();
if (distBee[x][y] == minutes-1 && !MechoIn) {
// for (int a=0; a<N; a++) {
// for (int b=0; b<N; b++) {
// cout << used[a][b] << " ";
// }
// cout << nl;
// }
MechoIn = 1;
UsedMecho[Mecho.first][Mecho.second] = 1;
queue<pair<int, int>> MechoQ;
MechoQ.push({Mecho.first, Mecho.second});
q.push_back({1, MechoQ});
}
for (auto move: moves) {
int nx = x + move.first, ny = y + move.second;
//Siamo le api
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (grid[nx][ny] == 0 || grid[nx][ny] == 2 || used[nx][ny]) continue;
used[nx][ny] = 1;
distBee[nx][ny] = distBee[x][y] + 1;
UsedMecho[nx][ny] = 1;
last.push({nx, ny});
}
}
if (!last.empty()) q.push_back({0, last});
}
}
if (UsedMecho[Home.first][Home.second]) {
a = minutes+1;
}
else b = minutes-1;
}
cout << b << nl;
}
