#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; 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 (nx<0 || nx>=n || ny<0 || ny>=n) continue; if (grid[nx][ny]=='D') { return true; } if (grid[nx][ny]=='T') continue; if (walkingdist[nx][ny]==-1) { if (dist[nx][ny]>0){ if ((walkingdist[x][y]+1)%speed==0) { if ((walkingdist[x][y]+speed-1)/speed+lag<dist[nx][ny]) { walkingdist[nx][ny]=walkingdist[x][y]+1; q.push({nx,ny}); } } else { if ((walkingdist[x][y]+speed-1)/speed+lag-1<dist[nx][ny]) { walkingdist[nx][ny]=walkingdist[x][y]+1; q.push({nx,ny}); } } } if (dist[nx][ny]==-1 && grid[nx][ny]=='G') { walkingdist[nx][ny]=walkingdist[x][y]+1; q.push({nx,ny}); } } } } // for (int i=0;i<n;i++) { // for (int j=0;j<n;j++) { // cout<<walkingdist[i][j]<<" "; // } // cout<<"\n"; // } // cout<<"\n"; 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"; int left=0,right=800*800; while (left<right) { int mid = left+(right-left+1)/2; if (bfs(mid)) left=mid; else right=mid-1; } cout<<left<<"\n"; }