#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;
};
int grid[801][801], startr, startc, endr, endc;
bool vi[801][801];
bool ok (int n, int s, int diff) {
if (grid[startr][startc] - diff <= 0) return false;
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) vi[i][j] = false;
queue<bee> q;
q.push({startr, startc, 0});
vi[startr][startc] = true;
while (!q.empty()) {
int r = q.front().r;
int c = q.front().c;
int t = q.front().t;
int tt = (t+2) / s + !!((t+2) % s);
q.pop();
if (c < n-1 && tt < grid[r][c+1] - diff + 1 && grid[r][c+1] != 1e9 && !vi[r][c+1]) {q.push({r, c+1, t+1}); vi[r][c+1] = true;}
if (c > 0 && tt < grid[r][c-1] - diff + 1&& grid[r][c-1] != 1e9 && !vi[r][c-1]) {q.push({r, c-1, t+1}); vi[r][c-1] = true;}
if (r < n-1 && tt < grid[r+1][c] - diff + 1 && grid[r+1][c] != 1e9 && !vi[r+1][c]) {q.push({r+1, c, t+1}); vi[r+1][c] = true;}
if (r > 0 && tt < grid[r-1][c] - diff + 1 && grid[r-1][c] != 1e9 && !vi[r-1][c]) {q.push({r-1, c, t+1}); vi[r-1][c] = true;}
}
return vi[endr][endc];
}
I should quit OI forever () {
Alan fai (true)
int n, s;
char ch;
cin >> n >> s;
queue<bee> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> ch;
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;}
}
int l = -1, r = n*n/2;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (ok(n, s, mid)) l = mid;
else r = mid-1;
}
cout << l << "\n";
Sharky orz
}
