#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <string>
using namespace std;
const int INF = 0x3f3f3f3f;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, S;
cin >> N >> S;
vector<string> grid(N);
for (int i = 0; i < N; i++){
cin >> grid[i];
}
// Locate Mecho's starting position (with the honeypot), his home, and all hives.
pair<int,int> start, dest;
vector<pair<int,int>> hives;
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
char c = grid[i][j];
if(c == 'M')
start = {i, j};
else if(c == 'D')
dest = {i, j};
else if(c == 'H')
hives.push_back({i, j});
}
}
// Directions for 4-way movement.
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
// ------------------------------
// 1. Precompute bees' arrival times.
// Starting from every hive at time 0, the bees spread (only through grassy cells, i.e.
// cells labeled 'G' or the honeypot 'M'). They never enter trees ('T') or Mecho's home ('D').
// ------------------------------
vector<vector<int>> beeTime(N, vector<int>(N, INF));
queue<pair<int,int>> qb;
for (auto &h : hives) {
int r = h.first, c = h.second;
beeTime[r][c] = 0;
qb.push({r, c});
}
while(!qb.empty()){
auto [r, c] = qb.front();
qb.pop();
int t = beeTime[r][c];
for (int d = 0; d < 4; d++){
int nr = r + dr[d], nc = c + dc[d];
if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
// Bees only spread into grassy cells (and the starting honeypot cell).
if(grid[nr][nc]=='G' || grid[nr][nc]=='M'){
if(beeTime[nr][nc] > t + 1){
beeTime[nr][nc] = t + 1;
qb.push({nr, nc});
}
}
}
}
// Mecho must leave his starting cell before the bees arrive there.
// Thus the maximum waiting time is beeTime[start] - 1.
int maxWait = (beeTime[start.first][start.second] == INF ? INF : beeTime[start.first][start.second] - 1);
// ------------------------------
// 2. Candidate check function (using a lambda).
// Given a candidate waiting time "waitTime" (in minutes that Mecho continues eating honey),
// we simulate his journey. At global time = waitTime he starts moving.
//
// In each minute of movement, he can take up to S steps. During each minute:
// - Every cell he passes (the "intermediate" cells) must be safe at the moment he
// is passing through (i.e. beeTime > global time).
// - If he "lands" at the end of the minute in a cell (unless it is his destination),
// that cell must remain safe one minute later (i.e. beeTime > global time + 1).
// We simulate minute–by–minute (outer BFS) and, within each minute, use a BFS to explore all
// reachable cells (up to S steps).
// ------------------------------
auto canReachHome = [&](int waitTime) -> bool {
// Check that the starting cell is safe when he begins moving.
if(beeTime[start.first][start.second] <= waitTime)
return false;
// moveTime[r][c] will record the minimum number of full minutes of movement needed to reach (r,c).
vector<vector<int>> moveTime(N, vector<int>(N, INF));
deque<pair<int,int>> dq;
moveTime[start.first][start.second] = 0;
dq.push_back({start.first, start.second});
while(!dq.empty()){
auto [r, c] = dq.front();
dq.pop_front();
int movesSoFar = moveTime[r][c];
int globalTime = waitTime + movesSoFar; // time at start of current minute
// If we've reached destination, we're safe.
if(r == dest.first && c == dest.second)
return true;
// From this cell, simulate a full minute of movement (up to S steps) using a local BFS.
vector<vector<int>> localDist(N, vector<int>(N, INF));
deque<pair<int,int>> localQ;
localDist[r][c] = 0;
localQ.push_back({r, c});
// We'll collect "landing positions" that are safe for ending the minute.
vector<pair<int,int>> nextPositions;
while(!localQ.empty()){
auto [cr, cc] = localQ.front();
localQ.pop_front();
int steps = localDist[cr][cc];
// Check landing: if we've moved at least 1 step and the cell is safe to "land"
// (either it's Mecho's home, or beeTime > globalTime+1).
if(steps > 0 && (grid[cr][cc]=='D' || beeTime[cr][cc] > globalTime + 1))
nextPositions.push_back({cr, cc});
// Also, if we reached the destination during movement, return true.
if(cr == dest.first && cc == dest.second)
return true;
if(steps == S) continue; // no more steps allowed in this minute.
for (int d = 0; d < 4; d++){
int nr = cr + dr[d], nc = cc + dc[d];
if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
// Mecho cannot go into trees or hives.
if(grid[nr][nc]=='T' || grid[nr][nc]=='H') continue;
// For intermediate traversal, the cell must be safe at time globalTime.
if(beeTime[nr][nc] <= globalTime)
continue;
if(localDist[nr][nc] > steps + 1){
localDist[nr][nc] = steps + 1;
localQ.push_back({nr, nc});
}
}
}
// For every landing position reached in this minute, add it for the next minute’s simulation.
for(auto &pos : nextPositions){
int nr = pos.first, nc = pos.second;
if(moveTime[nr][nc] > movesSoFar + 1){
moveTime[nr][nc] = movesSoFar + 1;
dq.push_back({nr, nc});
}
}
}
return false;
};
// ------------------------------
// 3. Binary search on waiting time.
// ------------------------------
int lo = 0, hi = maxWait, best = -1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(canReachHome(mid)){
best = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << best << "\n";
return 0;
}
