#include <bits/stdc++.h>
#define I using
#define WA using namespace std;
#define on using ll = long long;
#define Test(x) int AlanIQ = -(x);
#define should ld =
#define quit long double;
#define OI int
#define forever main
#define Alan cin.tie(0);
#define fai(x) ios::ios_base::sync_with_stdio(!x);
#define Sharky return
#define orz 0;
WA on Test (109)
struct bee {
int r, c, t;
};
I should quit OI forever () {
Alan fai (true)
int n, s;
char ch;
cin >> n >> s;
int grid[n][n], best[n][n], startr, startc, endr, endc;
queue<bee> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> ch;
best[i][j] = -1;
if (ch == 'T') grid[i][j] = 1e9;
else if (ch == 'G') grid[i][j] = 0;
else if (ch == 'M') {
startr = i;
startc = j;
grid[i][j] = 0;
} else if (ch == 'D') {
endr = i;
endc = j;
grid[i][j] = 1e8;
} else if (ch == 'H') {
q.push({i, j, 0});
grid[i][j] = 1e9;
}
}
}
while (!q.empty()) {
int r = q.front().r;
int c = q.front().c;
int t = q.front().t;
q.pop();
if (c < n-1 && !grid[r][c+1]) {q.push({r, c+1, t+1}); grid[r][c+1] = t+1;}
if (c > 0 && !grid[r][c-1]) {q.push({r, c-1, t+1}); grid[r][c-1] = t+1;}
if (r < n-1 && !grid[r+1][c]) {q.push({r+1, c, t+1}); grid[r+1][c] = t+1;}
if (r > 0 && !grid[r-1][c]) {q.push({r-1, c, t+1}); grid[r-1][c] = t+1;}
}
best[startr][startc] = 1e9;
q.push({startr, startc, 0});
while (!q.empty()) {
int r = q.front().r;
int c = q.front().c;
int t = q.front().t;
int ttt = (t+2) / s + !!((t+2) % s);
int cur = best[r][c];
q.pop();
if (c < n-1 && grid[r][c+1] != 1e9 && min(cur, grid[r][c+1]-ttt) > best[r][c+1]) {q.push({r, c+1, t+1}); best[r][c+1] = min(cur, grid[r][c+1]-ttt);}
if (c > 0 && grid[r][c-1] != 1e9 && min(cur, grid[r][c-1]-ttt) > best[r][c-1]) {q.push({r, c-1, t+1}); best[r][c-1] = min(cur, grid[r][c-1]-ttt);}
if (r < n-1 && grid[r+1][c] != 1e9 && min(cur, grid[r+1][c]-ttt) > best[r+1][c]) {q.push({r+1, c, t+1}); best[r+1][c] = min(cur, grid[r+1][c]-ttt);}
if (r > 0 && grid[r-1][c] != 1e9 && min(cur, grid[r-1][c]-ttt) > best[r-1][c]) {q.push({r-1, c, t+1}); best[r-1][c] = min(cur, grid[r-1][c]-ttt);}
}
cout << (best[endr][endc] >= 0 ? best[endr][endc] : -1) << "\n";
Sharky orz
}
