#include <bits/stdc++.h>
using namespace std;
const int NMAX = 8e2;
const int VISUAL = 4;
int dl[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
int n, step; int bee_dist[2 + NMAX][2 + NMAX];
char forest[2 + NMAX][2 + NMAX]; int dist[2 + NMAX][2 + NMAX];
pair<int, int> honey, house;
vector<pair<int, int>> bees;
void bee_spread () {
queue<pair<int, int>> q;
for ( auto pos : bees ) {
q.push ( pos );
bee_dist[pos.first][pos.second] = 1;
}
while ( !q.empty () ) {
pair<int, int> start = q.front (); q.pop ();
int line = start.first, column = start.second;
for ( int dir = 0; dir < VISUAL; dir ++ ) {
int new_line = line + dl[dir];
int new_col = column + dc[dir];
if ( forest[new_line][new_col] != 'T' && bee_dist[new_line][new_col] == 0 ) {
if ( forest[new_line][new_col] != 'D' ) {
q.push ( {new_line, new_col} );
bee_dist[new_line][new_col] = bee_dist[line][column] + 1;
}
}
}
}
}
bool validation ( int time, pair<int, int> start ) {
if ( time >= bee_dist[start.first][start.second] - 1 )
return false;
queue<pair<int, int>> q; q.push ( start );
dist[start.first][start.second] = 1;
while ( !q.empty () ) {
start = q.front (); q.pop ();
int line = start.first, column = start.second;
for ( int dir = 0; dir < VISUAL; dir ++ ) {
int new_line = line + dl[dir];
int new_col = column + dc[dir];
if ( new_line == house.first && new_col == house.second )
return true;
if ( (forest[new_line][new_col] == 'D' || forest[new_line][new_col] == 'G') && dist[new_line][new_col] == 0 ) {
dist[new_line][new_col] = dist[line][column] + 1;
int need = ( dist[new_line][new_col] - 1 ) / step;
if ( need + time < bee_dist[new_line][new_col] - 1 )
q.push ( {new_line, new_col} );
}
}
}
return false;
}
void reset_dist () {
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= n; j ++ )
dist[i][j] = 0;
}
void solve () {
int left = 0, right = 2 * n * n; int answer = -1;
while ( left <= right ) {
int time = left + (right - left) / 2;
int status = validation ( time, honey );
if ( status == true ) {
answer = time;
left = time + 1;
}
else
right = time - 1;
reset_dist ();
}
cout << answer;
}
int main()
{
cin >> n >> step; cin.get ();
for ( int line = 1; line <= n; line ++ ) {
for ( int column = 1; column <= n; column ++ ) {
forest[line][column] = cin.get ();
if ( forest[line][column] == 'M' )
honey = {line, column};
else if ( forest[line][column] == 'D' )
house = {line, column};
else if ( forest[line][column] == 'H' )
bees.push_back ( {line, column} );
}
cin.get ();
}
for ( int indx = 0; indx < n + 2; indx ++ ) {
forest[indx][0] = forest[indx][n + 1] = 'T';
forest[0][indx] = forest[n + 1][indx] = 'T';
}
bee_spread ();
solve ();
return 0;
}
