#include<bits/stdc++.h>
using namespace std;
#define cIO ios_base::sync_with_stdio(0);cin.tie(0)
#define fileIO(x) ifstream fin(string(x)+".in"); ofstream fout(string(x)+".out")
#define ll long long
#define coor pair<int,int>
#define row first
#define col second
#define sz(x) (int) (x).size()
#define v vector
#define f first
#define s second
#define pb push_back
#define at(arr, loc) arr[loc.first][loc.second]
int N, S;//size of map and maximum number of steps Mecho can take
int mr, mc, dr, dc;//row and colums of Mecho and his home
string forest[802];//the map of the forest
int d_to_H[802][802];//minimum distance of grass tile to hive, times S
int steps_M[802][802];//minimum, how many steps it takes for Mecho to get to a tile
int steps_rest[802][802];//minimum, how many STEPS Mecho can eat honey for so that he can still get to the tile before the bees
queue<coor> bfs_H;//bfs for hive
queue<coor> bfs_M;
string filler;//"TTTTT...T"
int rd[] = { 1,0,-1,0 }, cd[] = { 0,1,0,-1 };//delta r and c for a move
void debug(string name, int x)
{
cout << name << ": " << x << "\n";
}
void debug(string name, coor x)
{
cout << name << ": " << x.row << "," << x.col << "\n";
}
int main()
{
for (int i = 0; i <= 801; i++)
{
fill_n(d_to_H[i], 802, INT_MAX - 5);
fill_n(steps_M[i], 802, INT_MAX - 5);
fill_n(steps_rest[i], 802, 0);
}
//input
cIO;
cin >> N >> S;
for (int i = 0; i <= N + 1; i++) filler += "T";
forest[0] = forest[N + 1] = filler;
for (int i = 1; i <= N; i++)
{
cin >> forest[i];
forest[i] = string("T") + forest[i] + string("T");
for (int j = 1; j <= N; j++)
{
if (forest[i][j] == 'M')
{
mr = i; mc = j;
bfs_M.push({ i,j });
steps_M[i][j] = 0;
steps_rest[i][j] = INT_MAX - 5;
}//Mecho's location
else if (forest[i][j] == 'D') { dr = i; dc = j; }
else if (forest[i][j] == 'H')
{
bfs_H.push({ i,j });
d_to_H[i][j] = 0;
}
}
}
//compute d_to_H
while (!bfs_H.empty())
{
coor cur = bfs_H.front(); bfs_H.pop();
for (int i = 0; i <= 3; i++)
{
coor move;//next time, bees will try to move here (x4 cause 4 directions)
move.row = cur.row + rd[i];
move.col = cur.col + cd[i];
if (at(forest, move)=='G' && at(d_to_H, cur) + S < at(d_to_H, move))//if bees can move there, try
{
at(d_to_H, move) = at(d_to_H, cur) + S;
bfs_H.push(move);
}
}
}
//bfs on Mecho
while (!bfs_M.empty())
{
coor cur = bfs_M.front(); bfs_M.pop();
int next_st = at(steps_M, cur) + 1;
//debug("cur", cur);
for (int i = 0; i <= 3; i++)
{
coor move;//next time, bees will try to move here (x4 cause 4 directions)
move.row = cur.row + rd[i];
move.col = cur.col + cd[i];
//debug("move", move);
if (at(forest, move) == 'G'
|| at(forest, move) == 'D')//whether moving onto it is allowed
if (min(at(d_to_H, move) - 1 - next_st, at(steps_rest, cur)) > at(steps_rest, move)
&& next_st < at(d_to_H, move)
)//whether has more rest than current route, and can reach before bees
{
at(steps_M, move) = next_st;
at(steps_rest, move) = min(at(d_to_H, move) - 1 - next_st, at(steps_rest, cur));
//debug("d_to_H[move]", at(d_to_H, move));
//debug("steps_M[move]", at(steps_M, move));
//debug("steps_rest[move]", at(steps_rest, move));
bfs_M.push(move);
}
}
}
if (at(steps_rest, coor(dr, dc)) == INT_MAX - 5)
cout << "-1\n";
else cout << at(steps_rest, coor(dr, dc))/S << "\n";
return 0;
}
