#include <bits/stdc++.h> using namespace std; #define ll long long int n, m, x, y, u, v, k=-1; vector<vector<char>> a; vector<vector<int>> dist; vector<vector<pair<int, int>>> dis; int inf=1e9; void fl1() { queue<array<int, 2>> q; for(int i=0; i<n; i++) { for(int j=0; j<n; j++){if(a[i][j]=='H'){dist[i][j]=0; q.push({i, j});}} } while(!q.empty()) { auto u1=q.front(); q.pop(); if(u1[0]>0&&dist[u1[0]-1][u1[1]]>dist[u1[0]][u1[1]]+1&&(a[u1[0]-1][u1[1]]=='G'||a[u1[0]-1][u1[1]]=='M')) { dist[u1[0]-1][u1[1]]=dist[u1[0]][u1[1]]+1; q.push({u1[0]-1,u1[1]}); } if(u1[0]<n-1&&dist[u1[0]+1][u1[1]]>dist[u1[0]][u1[1]]+1&&(a[u1[0]+1][u1[1]]=='G'||a[u1[0]+1][u1[1]]=='M')) { dist[u1[0]+1][u1[1]]=dist[u1[0]][u1[1]]+1; q.push({u1[0]+1,u1[1]}); } if(u1[1]>0&&dist[u1[0]][u1[1]-1]>dist[u1[0]][u1[1]]+1&&(a[u1[0]][u1[1]-1]=='G'||a[u1[0]][u1[1]-1]=='M')) { dist[u1[0]][u1[1]-1]=dist[u1[0]][u1[1]]+1; q.push({u1[0],u1[1]-1}); } if(u1[1]<n-1&&dist[u1[0]][u1[1]+1]>dist[u1[0]][u1[1]]+1&&(a[u1[0]][u1[1]+1]=='G'||a[u1[0]][u1[1]+1]=='M')) { dist[u1[0]][u1[1]+1]=dist[u1[0]][u1[1]]+1; q.push({u1[0],u1[1]+1}); } } } bool solve(int x1) { if(x1>=dist[x][y]) return false; dis.assign(n, vector<pair<int, int>> (n)); for(int i=0; i<n; i++){for(int j=0; j<n; j++)dis[i][j]={inf, inf};} queue<array<int, 2>> q; q.push({x, y}); dis[x][y]={x1, 0}; while(!q.empty()) { auto u=q.front(); q.pop(); pair<int, int> ngh=dis[u[0]][u[1]]; ngh.second++; if(ngh.second==m){ngh.first++; ngh.second=0;} if(u[0]>0&&dist[u[0]-1][u[1]]>ngh.first&&ngh<dis[u[0]-1][u[1]]&&(a[u[0]-1][u[1]]!='T'&&a[u[0]-1][u[1]]!='H')) { dis[u[0]-1][u[1]]=ngh; if(a[u[0]-1][u[1]]=='D')return true; q.push({u[0]-1,u[1]}); } if(u[0]<n-1&&dist[u[0]+1][u[1]]>ngh.first&&ngh<dis[u[0]+1][u[1]]&&(a[u[0]+1][u[1]]!='T'&&a[u[0]+1][u[1]]!='H')) { dis[u[0]+1][u[1]]=ngh;if(a[u[0]+1][u[1]]=='D')return true; q.push({u[0]+1,u[1]}); } if(u[1]>0&&dist[u[0]][u[1]-1]>ngh.first&&ngh<dis[u[0]][u[1]-1]&&(a[u[0]][u[1]-1]!='T'&&a[u[0]][u[1]-1]!='H')) { dis[u[0]][u[1]-1]=ngh; if(a[u[0]][u[1]-1]=='D')return true; q.push({u[0],u[1]-1}); } if(u[1]<n-1&&dist[u[0]][u[1]+1]>ngh.first&&ngh<dis[u[0]][u[1]+1]&&(a[u[0]][u[1]+1]!='T'&&a[u[0]][u[1]+1]!='H')) { dis[u[0]][u[1]+1]=ngh; if(a[u[0]][u[1]+1]=='D')return true; q.push({u[0],u[1]+1}); } } return false; } int main() { cin>>n>>m; a.assign(n, vector<char> (n));dist.assign(n, vector<int> (n, inf)); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { cin>>a[i][j]; if(a[i][j]=='M'){x=i; y=j;} if(a[i][j]=='D'){u=i; v=j;} } } fl1(); int l=0, r=inf; while(l<=r) { int m=(l+r)/2; if(solve(m)){k=m; l=m+1;} else r=m-1; } cout<<k<<endl; }