#include <bits/stdc++.h> using namespace std; vector<vector<char>> grid; vector<vector<int>> dist; pair<int,int> start,dest; vector<pair<int,int>> hives; int n,speed; int dx[] = {1,0,-1,0}; int dy[] = {0,1,0,-1}; bool bfs(int lag) { if (dist[start.first][start.second] != -1 && dist[start.first][start.second] <= lag) return false; auto valid_sq = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < n && (grid[x][y] == 'G' || grid[x][y] == 'M'); }; auto mecho_reached = [&](int mecho_steps, int bees_steps_after_wait) { return mecho_steps / speed < bees_steps_after_wait; }; vector<vector<int>> walkingdist(n, vector<int>(n, -1)); queue<pair<int,int>> q; q.push(start); walkingdist[start.first][start.second] = 0; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (!valid_sq(nx, ny)) continue; if (walkingdist[nx][ny] != -1) continue; int stepsNext = walkingdist[x][y] + 1; if (dist[nx][ny] == -1) { walkingdist[nx][ny] = stepsNext; q.push({nx, ny}); continue; } int beeSlack = dist[nx][ny] - lag; if (beeSlack <= 0) continue; if (mecho_reached(stepsNext, beeSlack)) { walkingdist[nx][ny] = stepsNext; q.push({nx, ny}); } } } for (int i = 0; i < 4; i++) { int nx = dest.first + dx[i]; int ny = dest.second + dy[i]; if (!valid_sq(nx, ny)) continue; if (walkingdist[nx][ny] == -1) continue; if (dist[nx][ny] == -1) return true; int beeSlack = dist[nx][ny] - lag; if (beeSlack <= 0) continue; if (mecho_reached(walkingdist[nx][ny], beeSlack)) return true; } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); //freopen("1.in","r",stdin); cin>>n>>speed; grid.resize(n,vector<char>(n)); dist.resize(n,vector<int>(n,-1)); for (int i=0;i<n;i++) { for (int j=0;j<n;j++) { cin>>grid[i][j]; if (grid[i][j]=='H') { hives.push_back({i,j}); dist[i][j]=0; } else if (grid[i][j]=='T') { dist[i][j]=9; } else if (grid[i][j]=='M') start={i,j}; else if (grid[i][j]=='D') dest={i,j}; } } queue<pair<int,int>> q; for (auto [x,y]:hives) q.push({x,y}); while (!q.empty()) { auto [x,y] = q.front(); q.pop(); for (int i=0;i<4;i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx<0 || nx>=n || ny<0 || ny>=n) continue; if (grid[nx][ny]=='T') continue; if (grid[nx][ny]=='D') continue; if (dist[nx][ny]==-1) { dist[nx][ny]=dist[x][y]+1; q.push({nx,ny}); } } } // for (int i=0;i<n;i++) { // for (int j=0;j<n;j++) { // cout<<dist[i][j]<<" "; // } // cout<<"\n"; // } // cout<<"\n"; if (!bfs(0)) { cout<<-1<<"\n"; return 0; } int left=0,right=n*n; while (left<right) { int mid = left+(right-left+1)/2; if (bfs(mid)) left=mid; else right=mid-1; } cout<<left<<"\n"; }