#include <bits/stdc++.h>
using namespace std;
// A large number used as “infinity”
const int INF = 1000000000;
// Global direction arrays for 4‐way movement.
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
// Main
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];
}
pair<int,int> start, dest;
vector<pair<int,int>> hives;
// Scan the grid for special cells.
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});
}
}
}
// ------------------------------
// 1. Precompute bees arrival times.
//
// Bees start at every hive (arrival time 0).
// Then, at the end of each minute they “spread” to every adjacent grassy cell.
// (Grassy means cells with 'G' or the honeypot cell 'M'.)
// Note: The bees do not go into trees ('T') or Mecho’s home ('D').
// ------------------------------
vector<vector<int>> beeTime(N, vector<int>(N, INF));
queue<pair<int,int>> bq;
for(auto &h : hives){
int r = h.first, c = h.second;
beeTime[r][c] = 0;
bq.push({r, c});
}
while(!bq.empty()){
auto [r,c] = bq.front();
bq.pop();
int t = beeTime[r][c];
for (int i = 0; i < 4; i++){
int nr = r + dr[i], nc = c + dc[i];
if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
// Bees only spread into cells that are grassy.
if(grid[nr][nc]=='G' || grid[nr][nc]=='M'){
if(beeTime[nr][nc] > t + 1){
beeTime[nr][nc] = t + 1;
bq.push({nr, nc});
}
}
}
}
// ------------------------------
// 2. Binary search for the maximum number of minutes X that Mecho can wait.
//
// The idea is to test a candidate waiting time X.
// (Recall: if Mecho waits X minutes then at time X he leaves.
// During the next moves (each one lasting one minute) he must avoid cells
// that “fill up” with bees. In particular, when beginning a move at global time T = X+m,
// he may travel (up to S steps) only through cells u with beeTime[u] > T.
// If he chooses to “stop” (end his move) in a cell (other than his home D)
// then we require beeTime[u] > T+1, because the bees spread after his move.)
// ------------------------------
int low = 0;
// Mecho must leave from start before bees come in:
// so the maximum waiting time is at most beeTime[start]-1.
int high = (beeTime[start.first][start.second] == INF ? INF : beeTime[start.first][start.second] - 1);
int ans = -1;
// This lambda returns true if Mecho can reach D if he waits X minutes.
auto canReach = [&](int X) -> bool {
// Check that his starting cell is still safe when he starts (global time = X).
if(beeTime[start.first][start.second] <= X) return false;
// We use a “minute‐level” BFS.
// State: (cell, m) where m = number of move–minutes already used.
// Global time = X + m.
vector<vector<int>> moveTime(N, vector<int>(N, INF));
queue<pair<int,int>> mq;
moveTime[start.first][start.second] = 0;
mq.push(start);
int currentMove = 0;
while(!mq.empty()){
// Collect all cells reached at move count = currentMove.
vector<pair<int,int>> startCells;
int qs = mq.size();
while(qs--){
auto cell = mq.front(); mq.pop();
if(moveTime[cell.first][cell.second] == currentMove)
startCells.push_back(cell);
}
int globalTime = X + currentMove; // time at beginning of this move.
// For the current move (lasting one minute), from all startCells, we now determine
// the cells that can be reached in at most S steps.
// In the movement during the minute, every traversed cell must be safe at time "globalTime",
// i.e. beeTime > globalTime.
// And if Mecho chooses to “stop” in a cell (landing cell) at the end of the minute,
// then (unless it is his home D) that cell must satisfy beeTime > globalTime+1.
vector<vector<int>> localDist(N, vector<int>(N, INF)); // steps in current move
deque<pair<int,int>> dq;
// Initialize multi–source BFS for this move.
for(auto &p: startCells){
int r = p.first, c = p.second;
if(localDist[r][c] > 0){
localDist[r][c] = 0;
dq.push_back({r,c});
}
}
// nextPositions will hold the cells where Mecho can finish his move.
vector<pair<int,int>> nextPositions;
while(!dq.empty()){
auto [r,c] = dq.front();
dq.pop_front();
int d = localDist[r][c];
if(d == S) continue; // can’t move further in this minute.
for (int i = 0; i < 4; i++){
int nr = r + dr[i], nc = c + dc[i];
if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if(localDist[nr][nc] <= d+1) continue;
// Mecho cannot walk into obstacles (T or H).
if(grid[nr][nc]=='T' || grid[nr][nc]=='H') continue;
// For traversal, the cell must be safe at globalTime.
if(beeTime[nr][nc] <= globalTime) continue;
localDist[nr][nc] = d+1;
dq.push_back({nr, nc});
// If he could finish his move here (i.e. “land” here), then:
// if the cell is D (home) then bees don’t matter.
// Otherwise, we require that beeTime > globalTime+1.
if(grid[nr][nc]=='D' || beeTime[nr][nc] > globalTime+1){
// If we haven't reached (nr,nc) in a smaller number of moves, record it.
nextPositions.push_back({nr, nc});
}
}
}
// Check if any landing position is the destination.
for(auto &p : nextPositions){
if(grid[p.first][p.second]=='D')
return true;
}
// Add all landing positions (if not already reached with fewer moves) to the BFS queue.
for(auto &p: nextPositions){
int r = p.first, c = p.second;
if(moveTime[r][c] > currentMove + 1){
moveTime[r][c] = currentMove + 1;
mq.push({r,c});
}
}
currentMove++;
}
return false;
};
// Binary search over X.
while(low <= high){
int mid = low + (high - low)/2;
if(canReach(mid)){
ans = mid; // mid is feasible.
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << ans << "\n";
return 0;
}
